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 

Imports System.Console
Module Module9
    Sub main()
        Dim byk, k, l, m, n As Integer
        Write("Banyak angka : ")
        byk = ReadLine()

        Dim h(byk - 1) As Integer
        For k = 1 To byk
            Write("Angka ke-{0} : ", k)
            h(k - 1) = ReadLine()
        Next

        l = 0
        Do
            l = 3 * l + 1
        Loop Until l > byk - 1
        Do
            l /= 3
            For k = l To byk - 1
                m = h(k)
                n = k
                Do While h(n - l) > m
                    h(n) = h(n - l)
                    n -= l
                    If n < l Then Exit Do
                Loop
                h(n) = m
            Next
        Loop Until l = 0
        WriteLine()
        WriteLine("Hasil : ")
        For k = 1 To byk
            Write(h(k - 1) & " ")
        Next
        ReadKey()
    End Sub
End Module