LANJUTAN DARI SHORTING

LANJUTAN DARI SHORTING

PENGERTIAN SHELL SORT

Shell Sort

            Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu.

Insertion sort membandingkan elemen–elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya.

Program tentang merge sort

void mergesort (int *x, int n)

{

int *r, i, j, k, l1, l2, u1, u2, size;

r = (int *) malloc (n * sizeof (int));

size = 1;

while (size < n)

{

l1 = 0; k = 0;

while (l1+size < n)

{

l2 = l1+size;

u1 = l2 – 1;

u2 = (l2 + size – 1 < n) ? l2 + size – 1 : n-1;

for (i=l1; j=l2; i<=u1 && j<=u2; k++)

r[k] = (x[i] <= x[j]) ? x[i++] : x[j++];

while (i<=u1) r[k++] = x[i++];

while (j<=u2) r[k++] = x[j++];

l1 = u2+1;

}

for(i=l1; k<n; i++) r[k++] = x[i];

for(i=0; i<n; i++) x[i] = r[i];

size *= 2;

}

free(r); }a

KELEBIHAN DAN KELEMAHAN SORT

KELEBIHAN SORT :

      1. Sederhana dalam penerapannya.

      2. Mangkus dalam data yang kecil.

      3. Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat                   dibandingkan dengan Quicksort.

      4. Mangkus dalam data yang sebagian sudah terurut.

      5. Lebih mangkus dibanding Bubble Sort dan Selection Sort.

      6. Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu   algoritma pengurutan tercepat pada jumlah elemen yang sedikit.

      7. Stabil.

KELEMAHAN :

      1. Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk            elemen larik.

     2. Untuk larik yang jumlahnya besar ini tidak praktis.

     3. Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus       memindai dan mengganti seluruh bagian sebelum menyisipkan elemen            berikutnya.

     4. Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok       dalam pengurutan             elemen dalam jumlah besar.

 

METODE – METODE PENERAPAN SORT

1.        Comparison-Based Sorting (pengurutan berdasarkan perbandingan)
     # Bubble sort, exchange sort.

2.     Priority Queue Sorting Method (pengurutan berdasarkan prioritas)
    # Selection sort, heap sort.

3.     Insert and Keep Sorted Method (pengurutan berdasarkan penyisipan          dan penjagaan terurut) # Insertion sort, tree sort.

4.     Devide and Conquer Method(pengurutan berdasarkan pembagian dan          penguasaan) # Quick sort, merge sort.

5.    Diminishing Increment Sort Method (pengurutan berkurang menurun)
     # Shell sort.

Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :

1.  Algoritma pengurutan maksimum (maximum selection sort), yaitu memilih elemen maksimum sebagai basis pengurutan.

2. Algoritma pengurutan minimum (minimum selection sort), yaitu memilih elemen minimum sebagai basis pengurutan