Perhatikan angka-angka berikut:
50 60 30 10 80 70 20 40
Jika daftar ini diurutkan dalam urutan menaik, itu akan menjadi:
10 20 30 40 50 60 70 80
Jika diurutkan dalam urutan menurun, itu akan menjadi:
80 70 60 50 40 30 20 10
Insertion sort adalah algoritma pengurutan yang digunakan untuk mengurutkan daftar dalam urutan menaik atau menurun. Artikel ini hanya membahas pengurutan dalam urutan menaik. Penyortiran dalam urutan menurun mengikuti logika yang sama yang diberikan dalam dokumen ini. Tujuan dari artikel ini adalah untuk menjelaskan jenis penyisipan. Pemrograman dilakukan dalam contoh berikut di C. Pengurutan penyisipan dijelaskan di sini menggunakan satu larik.
Algoritma untuk Insertion Sort
Daftar yang tidak disortir diberikan. Tujuannya adalah untuk mengurutkan daftar dalam urutan menaik menggunakan daftar yang sama. Mengurutkan array yang tidak disortir menggunakan array yang sama dikatakan mengurutkan di tempat. Pengindeksan berbasis nol digunakan di sini. Langkah-langkahnya adalah sebagai berikut:
-
- Daftar dipindai dari awal.
- Saat pemindaian sedang berlangsung, nomor apa pun yang kurang dari pendahulunya akan ditukar dengan pendahulunya.
- Pertukaran ini berlanjut di sepanjang daftar, sampai tidak mungkin lagi untuk bertukar.
- Saat pemindaian mencapai akhir, penyortiran selesai.
Ilustrasi Pengurutan Penyisipan
Ketika berhadapan dengan kompleksitas waktu, itu adalah kasus terburuk yang biasanya dipertimbangkan. Susunan terburuk untuk daftar sebelumnya adalah:
80 70 60 50 40 30 20 10
Ada delapan elemen dengan indeks dari nol hingga 7.
Pada indeks nol, pemindaian menjadi 80. Ini adalah satu gerakan. Gerakan yang satu ini adalah operasi. Ada total satu operasi sejauh ini (satu gerakan, tidak ada perbandingan, dan tidak ada pertukaran). Hasilnya adalah:
| 80 70 60 50 40 30 20 10
Pada indeks satu, ada pergerakan ke 70. 70 dibandingkan dengan 80. 70 dan 80 ditukar. Satu gerakan adalah satu operasi. Satu perbandingan juga merupakan satu operasi. Satu swap juga merupakan satu operasi. Bagian ini menyediakan tiga operasi. Ada total empat operasi sejauh ini (1 + 3 = 4). Hasilnya adalah sebagai berikut:
70 | 80 60 50 40 30 20 10
Pada indeks dua, ada pergerakan ke 60. 60 dibandingkan dengan 80, kemudian 60 dan 80 ditukar. 60 dibandingkan dengan 70, kemudian 60 dan 70 ditukar. Satu gerakan adalah satu operasi. Dua perbandingan adalah dua operasi. Dua swap adalah dua operasi. Bagian ini menyediakan lima operasi. Ada total sembilan operasi sejauh ini (4 + 5 = 9). Hasilnya adalah sebagai berikut:
60 70 | 80 50 40 30 20 10
Pada indeks tiga, ada pergerakan ke 50. 50 dibandingkan dengan 80, kemudian 50 dan 80 ditukar. 50 dibandingkan dengan 70, kemudian 50 dan 70 ditukar. 50 dibandingkan dengan 60, kemudian 50 dan 60 ditukar. Satu gerakan adalah satu operasi. Tiga perbandingan adalah tiga operasi. Tiga swap adalah tiga operasi. Bagian ini menyediakan tujuh operasi. Ada total enam belas operasi sejauh ini (9 + 7 = 16). Hasilnya adalah sebagai berikut:
50 60 70 | 80 40 30 20 10
Pada indeks empat, ada pergerakan ke 40. 40 dibandingkan dengan 80, kemudian 40 dan 80 ditukar. 40 dibandingkan dengan 70, kemudian 40 dan 70 ditukar. 40 dibandingkan dengan 60, kemudian 40 dan 60 ditukar. 40 dibandingkan dengan 50, kemudian 40 dan 50 ditukar. Satu gerakan adalah satu operasi. Empat perbandingan adalah empat operasi. Empat swap adalah empat operasi. Bagian ini menyediakan sembilan operasi. Ada total dua puluh lima operasi sejauh ini (16 + 9 = 25). Hasilnya adalah sebagai berikut:
40 50 60 70 80 | 30 20 10
Pada indeks lima, ada pergerakan ke 30. 30 dibandingkan dengan 80, kemudian 30 dan 80 ditukar. 30 dibandingkan dengan 70, kemudian 30 dan 70 ditukar. 30 dibandingkan dengan 60, kemudian 30 dan 60 ditukar. 30 dibandingkan dengan 50, kemudian 30 dan 50 ditukar. 30 dibandingkan dengan 40, kemudian 30 dan 40 ditukar. Satu gerakan adalah satu operasi. Lima perbandingan adalah lima operasi. Lima swap adalah lima operasi. Bagian ini menyediakan sebelas operasi. Ada total tiga puluh enam operasi sejauh ini (25 + 11 = 36). Hasilnya adalah sebagai berikut:
30 40 50 60 70 80 | 20 10
Pada indeks enam, ada pergerakan ke 20. 20 dibandingkan dengan 80, kemudian 20 dan 80 ditukar. 20 dibandingkan dengan 70, kemudian 20 dan 70 ditukar. 20 dibandingkan dengan 60, kemudian 20 dan 60 ditukar. 20 dibandingkan dengan 50, kemudian 20 dan 50 ditukar. 20 dibandingkan dengan 40, kemudian 20 dan 40 ditukar. 20 dibandingkan dengan 30, kemudian 20 dan 30 ditukar. Satu gerakan adalah satu operasi. Enam perbandingan adalah enam operasi. Enam swap adalah enam operasi. Bagian ini menyediakan tiga belas operasi. Ada total empat puluh sembilan operasi sejauh ini (36 + 13 = 49). Hasilnya adalah sebagai berikut:
20 30 40 50 60 70 80 | 10
Pada indeks tujuh, ada pergerakan ke 10. 10 dibandingkan dengan 80, kemudian 10 dan 80 ditukar. 10 dibandingkan dengan 70, kemudian 10 dan 70 ditukar. 10 dibandingkan dengan 60, kemudian 10 dan 60 ditukar. 10 dibandingkan dengan 50, kemudian 10 dan 50 ditukar. 10 dibandingkan dengan 30, kemudian 10 dan 40 ditukar. 10 dibandingkan dengan 30, kemudian 10 dan 30 ditukar. 10 dibandingkan dengan 20, kemudian 10 dan 20 ditukar. Satu gerakan adalah satu operasi. Tujuh perbandingan adalah tujuh operasi. Tujuh swap adalah tujuh operasi. Bagian ini menyediakan lima belas operasi. Ada total enam puluh empat operasi sejauh ini (49 + 15 = 64). Hasilnya adalah sebagai berikut:
10 20 30 40 50 60 70 80 10 |
Pekerjaan selesai! 64 operasi terlibat.
64 = 8 x 8 = 8 dua
Kompleksitas Waktu untuk Insertion Sort
Jika ada n elemen untuk diurutkan dengan Insertion Sort, jumlah maksimum operasi yang mungkin adalah n2, seperti yang ditunjukkan sebelumnya. Kompleksitas Waktu Pengurutan Penyisipan adalah:
Pada dua )
Ini menggunakan notasi Big-O. Notasi Big-O dimulai dengan O dalam huruf besar, diikuti dengan tanda kurung. Di dalam tanda kurung adalah ekspresi untuk jumlah operasi maksimum yang mungkin.
Pengkodean dalam C
Pada awal pemindaian, elemen pertama tidak dapat mengubah posisinya. Program ini pada dasarnya adalah sebagai berikut:
#sertakanpengurutan penyisipan batal ( int A [ ] , int N ) {
untuk ( ke dalam saya = 0 ; saya < N; saya++ ) {
int j = saya;
ketika ( SEBUAH [ j ] < SEBUAH [ j- 1 ] && j- 1 > = 0 ) {
int suhu = A [ j ] ; SEBUAH [ j ] = A [ j- 1 ] ; SEBUAH [ j- 1 ] = suhu; // menukar
j--;
}
}
}
Definisi fungsi insertionSort() menggunakan algoritme seperti yang dijelaskan. Perhatikan kondisi perulangan while. Fungsi utama C yang cocok untuk program ini adalah:
{
int n = 8 ;
int A [ ] = { lima puluh , 60 , 30 , 10 , 80 , 70 , dua puluh , 40 } ;
penyisipanSort ( Sebuah ) ;
untuk ( ke dalam saya = 0 ; saya < n; saya++ ) {
printf ( '%saya ' , SEBUAH [ saya ] ) ;
}
printf ( ' \n ' ) ;
kembali 0 ;
}
Kesimpulan
Kompleksitas waktu untuk Insertion Sort diberikan sebagai:
Pada dua )
Pembaca mungkin pernah mendengar tentang kompleksitas waktu kasus yang lebih buruk, kompleksitas waktu kasus rata-rata dan kompleksitas waktu kasus terbaik. Variasi Kompleksitas Waktu Pengurutan Penyisipan ini dibahas dalam artikel berikutnya di situs web kami.