Struktur Data dan Urutan Penyisipan Algoritma
Ini adalah algoritme pengurutan berbasis perbandingan di tempat. Di sini, sub-daftar dipertahankan yang selalu diurutkan. Misalnya, bagian bawah larik dipertahankan untuk diurutkan. Sebuah elemen yang akan 'disisipkan' dalam sub-daftar yang diurutkan ini, harus menemukan tempat yang sesuai dan kemudian harus disisipkan di sana. Maka nama,insertion sort.
Array dicari secara berurutan dan item yang tidak diurutkan dipindahkan dan dimasukkan ke dalam sub-list yang diurutkan (dalam array yang sama). Algoritma ini tidak cocok untuk kumpulan data besar karena kompleksitas kasus rata-rata dan terburuk adalah (n 2 ), di manan adalah jumlah item.
Bagaimana Cara Kerja Insertion Sort?
Kami mengambil array yang tidak disortir untuk contoh kami.
Sortir penyisipan membandingkan dua elemen pertama.
Ia menemukan bahwa 14 dan 33 sudah dalam urutan naik. Untuk saat ini, 14 ada di sub-daftar yang diurutkan.
Urutan penyisipan bergerak maju dan membandingkan 33 dengan 27.
Dan menemukan bahwa 33 tidak dalam posisi yang benar.
Ini menukar 33 dengan 27. Ia juga memeriksa dengan semua elemen sub-daftar yang diurutkan. Di sini kita melihat bahwa sub-daftar yang diurutkan hanya memiliki satu elemen 14, dan 27 lebih besar dari 14. Oleh karena itu, sub-daftar yang diurutkan tetap diurutkan setelah bertukar.
Sekarang kami memiliki 14 dan 27 di sub-daftar yang diurutkan. Selanjutnya, membandingkan 33 dengan 10.
Nilai-nilai ini tidak dalam urutan yang diurutkan.
Jadi kami menukar mereka.
Namun, pertukaran membuat 27 dan 10 tidak disortir.
Karenanya, kami menukar mereka juga.
Sekali lagi kami menemukan 14 dan 10 dalam urutan yang tidak diurutkan.
Kami menukar mereka lagi. Pada akhir iterasi ketiga, kami memiliki sub-daftar yang diurutkan dari 4 item.
Proses ini berlanjut hingga semua nilai yang tidak diurutkan tercakup dalam sub-daftar yang diurutkan. Sekarang kita akan melihat beberapa aspek pemrograman dari semacam penyisipan.
Algoritma
Sekarang kita memiliki gambaran yang lebih besar tentang bagaimana teknik pengurutan ini bekerja, sehingga kita dapat memperoleh langkah-langkah sederhana yang dengannya kita dapat mencapai pengurutan penyisipan.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Pseudocode
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure
Untuk mengetahui tentang implementasi insertion sort dalam bahasa pemrograman C, silakan klik di sini .