Algoritma Pengurutan Shell dengan CONTOH

Apa itu Penyortiran Shell

Metode Shell, atau pengurutan Shell dalam struktur Data, adalah algoritma pengurutan perbandingan di tempat yang efisien. Namanya diambil dari Donald Shell ketika dia mengajukan ide awal pada tahun 1959. Pengurutan shell adalah perpanjangan umum dari algoritma pengurutan penyisipan.

Ide dasar dari algoritma pengurutan ini adalah mengelompokkan elemen-elemen yang berjauhan dan mengurutkannya sesuai dengan itu. Kemudian secara bertahap memperkecil jarak di antara elemen-elemen tersebut. Pengurutan shell mengatasi kompleksitas waktu kasus rata-rata dari pengurutan penyisipan dengan membandingkan dan menukar elemen-elemen yang berjauhan.

Kesenjangan ini, yang dikenal sebagai interval, dikurangi berdasarkan beberapa rangkaian kesenjangan optimal. Waktu berjalannya shell sort juga bergantung pada urutan ini. Ada beberapa barisan gap, seperti barisan asli Shell, rumus Knuth, kenaikan Hibbard, dll. Urutan celah asli Shell adalah – n/2, n/4, n/8, ……….1

Algoritma Pengurutan Shell

Langkah-langkah atau prosedur algoritma shell sort adalah sebagai berikut-

Langkah 1) Inisialisasi nilai interval, h = n/2. (Dalam contoh ini, n adalah ukuran array)

Langkah 2) Letakkan semua elemen dalam jarak interval h dalam sub-daftar.

Langkah 3) Urutkan sub-daftar tersebut menggunakan jenis penyisipan.

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

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

Langkah 6) Output yang dihasilkan akan menjadi array yang diurutkan.

Cara Kerja Penyortiran Shell

Dalam jenis penyisipan, elemen dipindahkan hanya satu posisi pada satu waktu. Sebaliknya, shell sort membagi array menjadi bagian-bagian yang lebih kecil berdasarkan nilai interval dan mengeksekusi penyisipan pada bagian-bagian tersebut.

Secara bertahap, nilai interval berkurang, dan ukuran potongan yang terbagi bertambah. Karena potongan-potongan tersebut telah disortir satu per satu sebelumnya, penggabungan potongan-potongan tersebut memerlukan langkah yang lebih sedikit dibandingkan sebelumnya jenis penyisipan.

GIF berikut menunjukkan demonstrasi pengurutan shell. Dalam demo ini, nilai yang ditunjukkan merah dan biru dibandingkan dan ditukar berdasarkan pengurutan penyisipan. Kemudian intervalnya berkurang, dan pengurutan shell memulai pengurutan penyisipan pada data yang hampir terurut tersebut.

Cara Kerja Algoritma Shell Sort

Mari kita lihat contoh berikut dari algoritma shell sort. Dalam contoh ini, kita akan mengurutkan array berikut menggunakan shell sort:

Langkah 1) Di sini, ukuran arraynya adalah 8. Jadi, nilai intervalnya adalah h = 8/2 atau 4.

Langkah 2) Sekarang, kita akan menyimpan semua elemen pada jarak 4. Untuk kasus kita, sublistnya adalah- {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Langkah 3) Sekarang, subdaftar tersebut akan diurutkan menggunakan jenis penyisipan, di mana variabel sementara digunakan untuk membandingkan kedua angka dan mengurutkannya sesuai dengan itu.

Susunannya akan seperti berikut setelah operasi pertukaran-

Langkah 4) Sekarang, kita akan menurunkan nilai awal intervalnya. Interval barunya adalah h=h/2 atau 4/2 atau 2.

Langkah 5) Sebagai 2>0, kita akan melanjutkan ke langkah 2 untuk menyimpan semua elemen pada jarak 2. Untuk kali ini, sublistnya adalah-

{1, 5, 8, 7}, {4, 2, 6, 3}

Kemudian sublist ini akan diurutkan menggunakan insertion sort. Setelah membandingkan dan menukar sublist pertama, susunannya akan menjadi sebagai berikut.

Setelah mengurutkan sublist kedua, array aslinya akan menjadi:

Kemudian lagi, intervalnya akan dikurangi. Sekarang intervalnya adalah h=h/2 atau 2/1 atau 1. Oleh karena itu kita akan menggunakan algoritma pengurutan penyisipan untuk mengurutkan array yang dimodifikasi.

Berikut ini adalah penggambaran prosedur penyisipan, langkah demi langkah.

Intervalnya dibagi lagi dengan 2. Pada saat ini, intervalnya menjadi 0. Jadi kita lanjutkan ke langkah 6.

Langkah 6) Karena intervalnya adalah 0, array diurutkan berdasarkan waktu ini. Array yang diurutkan adalah-

Kode Semu

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; 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

Berikut adalah aplikasi penting dari Shell Sort:

• Jenis shell digunakan di kernel Linux karena tidak menggunakan tumpukan panggilan.
• Perpustakaan uClibc menggunakan jenis Shell.
• Kompresor bzip2 menggunakan jenis Shell untuk menghentikan rekursi berlebih.

Kelebihan & Kekurangan Shell Sort

Kelebihan	Kekurangan
Tidak diperlukan panggilan tumpukan.	Tidak efisien untuk ukuran array yang besar.
Implementasi yang mudah.	Tidak efisien untuk elemen yang tersebar luas.
Efisien untuk elemen dengan jarak yang lebih kecil.

Analisis Kompleksitas Sortir Shell

Kompleksitas Waktu Sortir Shell

Kompleksitas waktu dari algoritma shell sort adalah O(n^2). Alasannya adalah sebagai berikut:

Untuk skenario terbaik, jumlah total pengujian untuk semua interval saat array sebelumnya disusun sama dengan log n. Dengan demikian, kompleksitasnya akan menjadi O(n*log n).

Untuk skenario terburuk, anggaplah array terdiri sedemikian rupa sehingga elemen-elemennya memerlukan jumlah perbandingan terbanyak. Kemudian semua elemen tidak akan dibandingkan dan dialihkan hingga iterasi terakhir. Oleh karena itu, total perbandingan yang diperlukan untuk kenaikan akhir adalah O(n^2).

Sebagai kesimpulan, kompleksitas waktu akan menjadi

1. Kompleksitas kasus terbaik: O(n*log n)
2. Kompleksitas kasus rata-rata: O(n*log n)
3. Kompleksitas kasus terburuk: O(n^2)

Kompleksitas waktu proses shell sort sangat bergantung pada urutan penambahan gap yang digunakan. Namun, urutan penambahan terbaik untuk shell sort masih belum diketahui.

Kompleksitas Ruang Sortir Shell

Dalam perbandingan semacam ini, kita tidak memerlukan ruang bantu tambahan. Jadi kompleksitas ruang dari algoritma semacam ini adalah O(1).