Metode Pengurutan Shell Sort

SORTING

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

Contoh:
Data Acak    : 5 6 8 1 3 25 10
Ascending    : 1 3 5 6 8 10 25
Descending    : 25 10 8 6 5 3 1

Metode Pengurutan Data
1. Pengurutan berdasarkan perbandingan (comparison-based sorting)
   Bubble sort, exchange sort
2. Pengurutan berdasarkan prioritas (priority queue sorting method)
   Selection sort, heap sort (menggunakan tree)
3. Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
   Insertion sort, tree sort
4. Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)
   Quick sort, merge sort
5. Pengurutan berkurang menurun (diminishing increment sort method)
   Shell sort (pengembangan insertion)

SHELL SORT

Shell sort merupakan Metode Pertambahan Menurun yang dikembangkan oleh Donald L. Shell
(1959).Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga
dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.


Jarak yang digunakan disebut increment value, atau sequence number k
 Misal sekuens: 5,3,1
 Pengambilan sekuens bebas, asal menurun
• Jika k=5, maka sublistnya:
  • Data[0], Data[5], Data[10], …
  • Data[1], Data[6], Data[11], …
  • Data[2], Data[7], Data[12], …
• Jika k=3, maka sublistnya:
  • Data[0], Data[3], Data[6], …
  • Data[1], Data[4], Data[7], …
  • Data[2], Data[5], Data[8], …

Pemilihan Sequence number
1. Disarankan jarak mula-mula dari data yang akan dibandingkan adalah (N/2)+1)
2. Pada proses berikutnya, digunakan jarak (N/4)+1)
3. Pada proses berikutnya, digunakan jarak (N/8)+1)
4. Demikian seterusnya sampai jarak yang digunakan adalah 1

Proses Pengurutannya
1. Untuk jarak (N/2)+1:
    - Data pertama (i=0) dibandingkan dengan data dengan jarak (N/2)+1. Apabila data pertama lebih besar    dari data ke (N/2)+1) tersebut maka kedua data tersebut ditukar.
    - Kemudian data kedua (i=1) dibandingkan dengan jarak yang sama yaitu (N/2)+1) = elemen ke-(i+N/2)+1
    - Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-i selalu lebih kecil dari pada data ke-(i+N/2)+1
2. Ulangi langakah-langkah diatas untuk jarak = (N/4)+1 kemudian lakukan pembandingan dan pengurutan sehingga semua data ke-i lebih kecil daripada data ke-(i+N/4)+1
3. Ulangi langakah-langkah diatas untuk jarak = (N/8)+1 kemudian lakukan pembandingan dan pengurutan sehingga semua data ke-i lebih kecil daripada data ke-(i+N/8)+1
4.  Demikian seterusnya sampai jarak yang digunakan adalah 1 atau data sudah terurut

Contoh:

Proses pertama, jarak=(N/2)+1=(8/2)+1=5

 Proses kedua, jarak=(N/4)+1=(8/4)+1=3

Proses ketiga, jarak=(N/8)=(8/4)=1