Kerumitan Masa Isih Sisipan

Pertimbangkan nombor berikut:

50 60 30 10 80 70 20 40

Jika senarai ini diisih dalam tertib menaik, ia akan menjadi:

10 20 30 40 50 60 70 80

Jika ia diisih dalam tertib menurun, ia akan menjadi:

80 70 60 50 40 30 20 10

Isih sisipan ialah algoritma pengisihan yang digunakan untuk mengisih senarai dalam tertib menaik atau dalam tertib menurun. Artikel ini hanya berkaitan dengan pengisihan dalam tertib menaik. Isih dalam tertib menurun mengikut logik yang sama yang diberikan dalam dokumen ini. Matlamat artikel ini adalah untuk menerangkan jenis sisipan. Pengaturcaraan dilakukan dalam contoh berikut dalam C. Isihan sisipan diterangkan di sini menggunakan satu tatasusunan.

Algoritma untuk Isih Sisipan

Senarai tidak diisih diberikan. Tujuannya adalah untuk mengisih senarai dalam susunan menaik menggunakan senarai yang sama. Mengisih tatasusunan yang tidak diisih menggunakan tatasusunan yang sama dikatakan mengisih di tempat. Pengindeksan berasaskan sifar digunakan di sini. Langkah-langkahnya adalah seperti berikut:

• • Senarai itu diimbas dari awal.
  • Semasa pengimbasan sedang dijalankan, sebarang nombor yang kurang daripada pendahulunya ditukar dengan pendahulunya.
  • Pertukaran ini berterusan di sepanjang senarai, sehingga tidak lagi boleh ditukar.
  • Apabila pengimbasan sampai ke penghujung, pengisihan selesai.

Ilustrasi Isih Sisipan

Apabila berurusan dengan kerumitan masa, ia adalah kes terburuk yang biasanya diambil kira. Susunan terburuk untuk senarai sebelumnya ialah:

80 70 60 50 40 30 20 10

Terdapat lapan elemen dengan indeks dari sifar hingga 7.

Pada indeks sifar, imbasan pergi ke 80. Ini adalah satu pergerakan. Pergerakan yang satu ini adalah operasi. Terdapat sejumlah satu operasi setakat ini (satu pergerakan, tiada perbandingan dan tiada pertukaran). Hasilnya ialah:

| 80 70 60 50 40 30 20 10

Pada indeks satu, terdapat pergerakan ke 70. 70 dibandingkan dengan 80. 70 dan 80 ditukar. Satu pergerakan adalah satu operasi. Satu perbandingan juga satu operasi. Satu swap juga satu operasi. Bahagian ini menyediakan tiga operasi. Terdapat empat operasi setakat ini (1 + 3 = 4). Hasilnya adalah seperti berikut:

70 | 80 60 50 40 30 20 10

Pada indeks dua, terdapat pergerakan ke 60. 60 dibandingkan dengan 80, kemudian 60 dan 80 ditukar. 60 dibandingkan dengan 70, kemudian 60 dan 70 ditukar. Satu pergerakan adalah satu operasi. Dua perbandingan adalah dua operasi. Dua swap ialah dua operasi. Bahagian ini menyediakan lima operasi. Terdapat sembilan operasi setakat ini (4 + 5 = 9). Hasilnya adalah seperti berikut:

60 70 | 80 50 40 30 20 10

Pada indeks tiga, terdapat 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 pergerakan adalah satu operasi. Tiga perbandingan ialah tiga operasi. Tiga swap adalah tiga operasi. Bahagian ini menyediakan tujuh operasi. Terdapat sejumlah enam belas operasi setakat ini (9 + 7 = 16). Hasilnya adalah seperti berikut:

50 60 70 | 80 40 30 20 10

Pada indeks empat, terdapat 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 pergerakan adalah satu operasi. Empat perbandingan ialah empat operasi. Empat swap ialah empat operasi. Bahagian ini menyediakan sembilan operasi. Terdapat sejumlah dua puluh lima operasi setakat ini (16 + 9 = 25). Hasilnya adalah seperti berikut:

40 50 60 70 80 | 30 20 10

Pada indeks lima, terdapat 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 pergerakan adalah satu operasi. Lima perbandingan ialah lima operasi. Lima swap ialah lima operasi. Bahagian ini menyediakan sebelas operasi. Terdapat sejumlah tiga puluh enam operasi setakat ini (25 + 11 = 36). Hasilnya adalah seperti berikut:

30 40 50 60 70 80 | 20 10

Pada indeks enam, terdapat 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 pergerakan adalah satu operasi. Enam perbandingan ialah enam operasi. Enam swap ialah enam operasi. Bahagian ini menyediakan tiga belas operasi. Terdapat sejumlah empat puluh sembilan operasi setakat ini (36 + 13 = 49). Hasilnya adalah seperti berikut:

20 30 40 50 60 70 80 | 10

Pada indeks tujuh, terdapat 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 pergerakan adalah satu operasi. Tujuh perbandingan ialah tujuh operasi. Tujuh pertukaran ialah tujuh operasi. Bahagian ini menyediakan lima belas operasi. Terdapat sejumlah enam puluh empat operasi setakat ini (49 + 15 = 64). Hasilnya adalah seperti berikut:

10 20 30 40 50 60 70 80 10 |

Kerja sudah selesai! 64 operasi terlibat.

64 = 8 x 8 = 8 ^dua

Kerumitan Masa untuk Isih Sisipan

Jika terdapat n elemen untuk diisih dengan Isih Sisipan, bilangan maksimum operasi yang mungkin ialah n2, seperti yang ditunjukkan sebelum ini. Kerumitan Masa Isih Sisipan ialah:

O(n ^dua )

Ini menggunakan tatatanda Big-O. Notasi Big-O bermula dengan O dalam huruf besar, diikuti dengan kurungan. Di dalam kurungan terdapat ungkapan untuk bilangan operasi maksimum yang mungkin.

Pengekodan dalam C

Pada permulaan imbasan, elemen pertama tidak boleh mengubah kedudukannya. Program ini pada dasarnya adalah seperti berikut:

Definisi fungsi insertionSort() menggunakan algoritma seperti yang diterangkan. Perhatikan syarat untuk gelung sementara. Fungsi utama C yang sesuai untuk program ini ialah:

Kesimpulan

Kerumitan masa untuk Isih Sisipan diberikan sebagai:

O(n ^dua )

Pembaca mungkin pernah mendengar tentang kerumitan masa kes yang lebih teruk, kerumitan masa kes purata dan kerumitan masa kes terbaik. Variasi Kerumitan Masa Isih Sisipan ini dibincangkan dalam artikel seterusnya di tapak web kami.