Algoritma Pengurutan Shell dengan Contoh

Apa itu Shell Sort?

Shell Sort, juga disebut metode Shell, adalah algoritma pengurutan berbasis perbandingan in-place yang efisien. Dinamakan berdasarkan Donald Shell, yang memperkenalkan ide tersebut pada tahun 1959, algoritma ini merupakan perluasan umum dari insertion sort yang mengatasi perilaku kuadratiknya pada data yang tersebar.

Ide dasarnya adalah mengelompokkan elemen-elemen yang berjauhan, mengurutkan setiap kelompok menggunakan pengurutan penyisipan (insertion sort), dan memperkecil jaraknya selangkah demi selangkah hingga mencapai satu. Pada saat itu, array hampir terurut.

Jeda ini, atau intervalnya, mengikuti urutan yang dipilih seperti versi asli Shell, Knuth, Hibbard, atau Sedgewick. Versi asli Shell adalah n/2, n/4, ..., 1.

Algoritma Pengurutan Shell

Langkah 1) Inisialisasi nilai interval h = n/2, di mana n adalah ukuran array.

Langkah 2) Tempatkan semua elemen dalam jarak interval h ke dalam subdaftar.

Langkah 3) Urutkan setiap subdaftar menggunakan pengurutan penyisipan (insertion sort).

Langkah 4) Tetapkan interval baru h = h/2.

Langkah 5) Jika h > 0, kembali ke Langkah 2. Jika tidak, lanjutkan ke Langkah 6.

Langkah 6) Array yang dihasilkan sekarang sudah sepenuhnya terurut.

Cara Kerja Penyortiran Shell

Pada pengurutan sisipan (insertion sort), elemen hanya bergerak satu posisi pada satu waktu. Sebaliknya, Shell Sort membagi array menjadi sublist yang berjarak cukup jauh berdasarkan interval dan menjalankan pengurutan sisipan pada setiap sublist.

Saat interval mengecil, ukuran sublist bertambah. Karena proses sebelumnya menyisakan data yang sebagian sudah diurutkan, interval yang lebih kecil membutuhkan pertukaran yang jauh lebih sedikit daripada menjalankan proses yang lebih panjang. jenis penyisipan dari awal. Gambar di bawah ini mengilustrasikan satu proses Shell Sort.

Cara Kerja Algoritma Pengurutan Shell dengan Contoh

Mari kita urutkan array di bawah ini menggunakan Shell Sort.

Langkah 1) Ukuran array adalah 8, jadi nilai interval awal adalah h = 8/2 = 4.

Langkah 2) Kelompokkan elemen-elemen yang berjarak empat posisi. Subdaftar: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Langkah 3) Urutkan setiap sublist menggunakan insertion sort. Variabel sementara menyimpan nilai yang ditempatkan saat elemen bergeser. Setelah pertukaran, array akan terlihat seperti ini.

Langkah 4) Perkecil intervalnya. Interval barunya adalah h = 4/2 = 2.

Langkah 5) Karena 2 > 0, kembali ke Langkah 2 dan kelompokkan elemen yang berjarak dua posisi: {1, 5, 8, 7} dan {4, 2, 6, 3}.

Urutkan sublist pertama. Array menjadi:

Setelah mengurutkan subdaftar kedua:

Kurangi interval lagi menjadi h = 2/2 = 1. Dengan celah satu, Shell Sort menjalankan proses pengurutan sisipan akhir di seluruh array, seperti yang ditunjukkan di bawah ini.

Langkah 6) Membagi interval lagi menghasilkan 0. Larik sekarang sudah sepenuhnya terurut:

Semu-Code untuk Shell Sort

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

Program Pengurutan Shell di C/C++

Memasukkan:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Keluaran:

Sorted Output:

1 2 3 4 5 6 7 8

Contoh Pengurutan Shell di Python

Memasukkan:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Keluaran:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Aplikasi Penyortiran Shell

Shell Sort masih muncul di sistem modern di mana ruang tumpukan atau kesederhanaan menjadi pertimbangan penting.

• The kernel Linux Menggunakan Shell Sort di tempat-tempat di mana menghindari tumpukan panggilan (call stack) menjadi penting.
• Pustaka C tersemat uClibc menggunakan Shell Sort untuk menjaga penggunaan memori tetap rendah.
• bzip2 menggunakan Shell Sort untuk menghindari rekursi mendalam selama pengurutan blok.
• Firmware tertanam lebih menyukai Shell Sort untuk kumpulan data kecil di mana rekursi dibatasi.

Keuntungan dan Kerugian dari Pengurutan Shell

Analisis Kompleksitas Sortir Shell

Kompleksitas Waktu Sortir Shell

Kompleksitas waktu dari Shell Sort bergantung pada urutan celah yang digunakan.

Dalam skenario terbaik, ketika susunan array sudah hampir sempurna, setiap tahapan hanya membutuhkan sejumlah pengujian logaritmik, sehingga menghasilkan kompleksitas waktu O(n log n).

Dalam kasus terburuk, larik diatur sedemikian rupa sehingga elemen-elemen membutuhkan perbandingan maksimum, dan penambahan terakhir mendominasi pada O(n^2) dengan urutan asli Shell.

1. Kompleksitas kasus terbaik: O(n log n)
2. Kompleksitas kasus rata-rata: O(n log n) hingga O(n^(4/3)) tergantung pada urutan celah.
3. Kompleksitas kasus terburuk: O(n^2) dengan urutan asli Shell.

Urutan celah serbaguna terbaik masih menjadi pertanyaan penelitian terbuka, meskipun urutan Sedgewick dan Ciura berkinerja baik dalam praktiknya.

Kompleksitas Ruang Sortir Shell

Algoritma Shell Sort tidak memerlukan array bantu, sehingga kompleksitas ruangnya adalah O(1) terlepas dari ukuran input, yang merupakan salah satu keunggulan praktis terkuatnya.

Pertanyaan Umum Demo Slot