Sortasi Penyisipan di Jawa

1. Ikhtisar

Dalam tutorial ini, kita akan membahas algoritma Insertion Sort dan melihat implementasi Java-nya .

Sortir Penyisipan adalah algoritme yang efisien untuk memesan sejumlah kecil item. Metode ini didasarkan pada cara pemain kartu mengurutkan tangan dari kartu remi.

Kami mulai dengan tangan kiri kosong dan kartu diletakkan di atas meja. Kami kemudian mengeluarkan satu kartu pada satu waktu dari meja dan memasukkannya ke posisi yang benar di tangan kiri. Untuk menemukan posisi yang benar untuk kartu baru, kami membandingkannya dengan set kartu yang sudah diurutkan di tangan, dari kanan ke kiri.

Mari kita mulai dengan memahami langkah-langkah algoritma dalam bentuk pseudocode.

2. Pseudocode

Kami akan menampilkan pseudocode kami untuk penyisipan sort sebagai prosedur yang disebut INSERTION-SORT , mengambil parameter array A [1 .. n] dari n item yang akan diurutkan. Algoritme mengurutkan larik masukan di tempat (dengan menata ulang item di dalam larik A).

Setelah prosedur selesai, larik input A berisi permutasi dari urutan input tetapi dalam urutan yang diurutkan:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Mari kita bahas algoritme di atas secara singkat.

Indeks i menunjukkan posisi item saat ini dalam larik untuk diproses.

Kami mulai dari item kedua karena menurut definisi, sebuah array dengan satu item dianggap diurutkan. Item di indeks i disebut kunci . Setelah memiliki kunci, bagian kedua dari algoritme berkaitan dengan menemukan indeks yang benar. Jika kunci lebih kecil dari nilai item pada indeks j , maka kunci tersebut berpindah satu posisi ke kiri. Proses berlanjut sampai kasus ketika kita mencapai elemen yang lebih kecil dari kunci.

Penting untuk diperhatikan bahwa sebelum memulai iterasi untuk menemukan posisi kunci yang benar pada indeks i , larik A [1 .. j - 1] sudah diurutkan .

3. Implementasi Imperatif

Untuk kasus imperatif, kita akan menulis fungsi yang disebut insertionSortImperative , dengan mengambil parameter array bilangan bulat. Fungsi mulai melakukan iterasi pada larik dari item kedua.

Pada waktu tertentu selama iterasi, kita dapat menganggap larik ini secara logis dibagi menjadi dua bagian; sisi kiri adalah diurutkan satu dan sisi kanan berisi item yang belum disortir.

Catatan penting di sini adalah bahwa setelah menemukan posisi yang benar untuk memasukkan item baru, kita menggeser (dan tidak menukar) item ke kanan untuk mengosongkan ruang untuknya.

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }
    

Selanjutnya, mari buat tes untuk metode di atas:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() { int[] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Pengujian di atas membuktikan bahwa algoritme mengurutkan dengan benar dalam urutan menaik array input .

4. Implementasi Rekursif

Fungsi untuk kasus rekursif disebut ekursif insertionSortR dan menerima input array bilangan bulat (sama seperti untuk kasus imperatif).

Perbedaan di sini dari kasus imperatif (terlepas dari kenyataan bahwa itu rekursif) adalah bahwa ia memanggil fungsi yang kelebihan beban dengan argumen kedua yang sama dengan jumlah item untuk diurutkan.

Karena kami ingin mengurutkan array lengkap, kami akan mengirimkan sejumlah item yang sama dengan panjangnya:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

Kasus rekursif sedikit lebih menantang. Kasus dasar terjadi ketika kita mencoba mengurutkan array dengan satu item. Dalam hal ini, kami tidak melakukan apa pun.

Semua panggilan rekursif berikutnya mengurutkan bagian yang telah ditentukan sebelumnya dari larik input - mulai dari item kedua hingga kita mencapai akhir larik:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

Dan seperti inilah tampilan stack panggilan untuk array input dari 6 item:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Mari kita lihat juga tesnya:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() { int[] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Pengujian di atas membuktikan bahwa algoritme mengurutkan dengan benar dalam urutan menaik array input .

5. Kompleksitas Ruang dan Waktu

Waktu yang dibutuhkan oleh prosedur INSERTION-SORT untuk menjalankan adalah O (n ^ 2) . Untuk setiap item baru, kita mengulang dari kanan ke kiri pada bagian array yang sudah diurutkan untuk menemukan posisi yang benar. Kemudian kami memasukkannya dengan menggeser item satu posisi ke kanan.

Algoritme mengurutkan di tempat sehingga kompleksitas ruangnya adalah O (1) untuk implementasi imperatif dan O (n) untuk implementasi rekursif.

6. Kesimpulan

Dalam tutorial ini, kami melihat bagaimana menerapkan semacam penyisipan.

Algoritma ini berguna untuk menyortir sejumlah kecil item. Ini menjadi tidak efisien saat mengurutkan urutan input yang memiliki lebih dari 100 item.

Perlu diingat bahwa terlepas dari kompleksitas kuadratnya, ia mengurutkan di tempat tanpa memerlukan ruang tambahan seperti halnya untuk jenis gabungan .

Seluruh kode dapat ditemukan di GitHub.