Sortir Shell di Java

1. Perkenalan

Dalam tutorial ini, kami akan menjelaskan algoritma sortir Shell di Java.

2. Ikhtisar Sortir Shell

2.1. Deskripsi

Pertama-tama, mari kita gambarkan algoritma sortir Shell sehingga kita tahu apa yang kita coba terapkan.

Pengurutan shell didasarkan pada algoritma pengurutan Penyisipan, dan itu termasuk dalam kelompok algoritma yang sangat efisien. Secara umum, algoritme memecah kumpulan asli menjadi subset yang lebih kecil dan kemudian masing-masing diurutkan menggunakan semacam penyisipan .

Namun, cara membuat subset tidak langsung. Itu tidak memilih elemen tetangga untuk membentuk subset seperti yang kita harapkan. Sebaliknya, jenis shell menggunakan apa yang disebut interval atau celah untuk pembuatan subset. Misalnya, jika kita memiliki celah I , itu berarti satu subset akan berisi elemen yang posisinya saya terpisah.

Pertama, algoritme mengurutkan elemen yang berada jauh dari satu sama lain. Kemudian, celah menjadi lebih kecil dan elemen yang lebih dekat dibandingkan. Dengan cara ini, beberapa elemen yang tidak pada posisi yang benar dapat diposisikan lebih cepat daripada jika kita membuat subset dari elemen tetangga.

2.2. Sebuah contoh

Mari kita lihat ini dalam contoh dengan celah 3 dan 1 dan daftar 9 elemen yang tidak diurutkan:

Jika kita mengikuti deskripsi di atas, pada iterasi pertama, kita akan memiliki tiga subset dengan 3 elemen (disorot dengan warna yang sama):

Setelah mengurutkan setiap subset di iterasi pertama, daftarnya akan terlihat seperti:

Kami dapat mencatat bahwa, meskipun kami belum memiliki daftar yang diurutkan, elemen sekarang lebih dekat ke posisi yang diinginkan.

Terakhir, kita perlu melakukan satu pengurutan lagi dengan penambahan satu dan itu sebenarnya jenis penyisipan dasar. Jumlah operasi pergeseran yang perlu kita lakukan untuk mengurutkan daftar sekarang lebih kecil daripada jika kita tidak melakukan iterasi pertama:

2.3. Memilih Urutan Gap

Seperti yang kami sebutkan, jenis shell memiliki cara unik untuk memilih urutan celah. Ini adalah tugas yang sulit dan kita harus berhati-hati untuk tidak memilih terlalu sedikit atau terlalu banyak celah. Rincian lebih lanjut dapat ditemukan di daftar urutan celah yang paling diusulkan.

3. Implementasi

Sekarang mari kita lihat implementasinya. Kami akan menggunakan urutan asli Shell untuk kenaikan interval:

N/2, N/4, …, 1 (continuously dividing by 2)

Implementasinya sendiri tidak terlalu rumit:

public void sort(int arrayToSort[]) { int n = arrayToSort.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arrayToSort[j - gap] > key) { arrayToSort[j] = arrayToSort[j - gap]; j -= gap; } arrayToSort[j] = key; } } }

Kami pertama kali membuat urutan celah dengan loop for dan kemudian melakukan sortir penyisipan untuk setiap ukuran celah.

Sekarang, kami dapat dengan mudah menguji metode kami:

@Test public void givenUnsortedArray_whenShellSort_thenSortedAsc() { int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort(input); int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals("the two arrays are not equal", expected, input); }

4. Kompleksitas

Secara umum, algoritma sortir Shell sangat efisien dengan daftar berukuran sedang . Kompleksitas sulit untuk ditentukan karena sangat bergantung pada urutan gap, tetapi kompleksitas waktu bervariasi antara O (N) dan O (N ^ 2) .

Kompleksitas ruang kasus terburuk adalah O (N) dengan O (1) ruang tambahan.

5. Kesimpulan

Dalam tutorial ini, kami menjelaskan jenis Shell dan mengilustrasikan bagaimana kami dapat menerapkannya di Java.

Seperti biasa, seluruh kode dapat ditemukan di GitHub.