Terdapat beberapa algoritma asas untuk menyelesaikan masalah menyusun tatasusunan. Salah satu yang paling terkenal di kalangan mereka ialah jenis sisipan. Oleh kerana kejelasan dan kesederhanaan, tetapi kecekapan rendah, kaedah ini digunakan terutamanya dalam pengajaran pengaturcaraan. Ia membolehkan anda memahami mekanisme pengisihan asas.
Penerangan tentang algoritma
Intipati algoritma isihan sisipan ialah segmen yang disusun dengan betul terbentuk di dalam tatasusunan awal. Setiap elemen dibandingkan satu persatu dengan bahagian yang ditanda dan dimasukkan ke tempat yang betul. Oleh itu, selepas mengulangi semua elemen, ia berbaris dalam susunan yang betul.
Turutan pemilihan elemen boleh menjadi apa-apa, ia boleh dipilih sewenang-wenangnya atau mengikut beberapa algoritma. Selalunya, penghitungan berjujukan digunakan dari permulaan tatasusunan, di mana segmen tersusun terbentuk.
Permulaan pengisihan mungkin kelihatan seperti ini:
- Ambil elemen pertama tatasusunan.
- Memandangkan tiada apa-apa untuk membandingkannya, ambil elemen itu sendiri seperti yang dipesanurutan.
- Pergi ke item kedua.
- Bandingkan dengan yang pertama berdasarkan peraturan isihan.
- Jika perlu, tukar elemen di tempat.
- Ambil dua elemen pertama sebagai urutan tertib.
- Pergi ke item ketiga.
- Bandingkan dengan yang kedua, tukar jika perlu.
- Jika penggantian dibuat, bandingkan dengan yang pertama.
- Ambil tiga elemen sebagai urutan tertib.
Dan seterusnya sehingga penghujung tatasusunan asal.
Isihan sisipan kehidupan sebenar
Untuk kejelasan, anda patut memberi contoh bagaimana mekanisme pengisihan ini digunakan dalam kehidupan seharian.
Ambil, sebagai contoh, dompet. Bil ratus, lima ratus dan ribuan dolar berada dalam keadaan tidak teratur dalam petak wang kertas. Ini adalah keadaan huru-hara, dalam hodgepodge seperti itu sukar untuk segera mencari sekeping kertas yang betul. Susunan wang kertas mesti diisih.
Yang pertama ialah wang kertas 1000 rubel, dan sejurus selepas itu - 100. Kami mengambil seratus dan meletakkannya di hadapan. Yang ketiga berturut-turut ialah 500 rubel, tempat yang sah untuknya adalah antara seratus dan seribu.
Dengan cara yang sama kami mengisih kad yang diterima semasa bermain "Fool" untuk memudahkan anda menavigasinya.
Fungsi pengendali dan pembantu
Kaedah isihan sisipan mengambil sebagai input tatasusunan awal untuk diisih, fungsi perbandingan dan, jika perlu, fungsi yang menentukan peraturan untuk menghitung unsur. Paling kerap digunakan sebaliknyapernyataan gelung biasa.
Elemen pertama itu sendiri adalah set tertib, jadi perbandingan bermula dari yang kedua.
Algoritma sering menggunakan fungsi pembantu untuk menukar dua nilai (swap). Ia menggunakan pembolehubah sementara tambahan, yang menggunakan memori dan melambatkan sedikit kod.
Alternatif ialah mengalihkan sekumpulan elemen secara besar-besaran dan kemudian memasukkan elemen semasa ke dalam ruang kosong. Dalam kes ini, peralihan kepada elemen seterusnya berlaku apabila perbandingan memberikan hasil yang positif, yang menunjukkan susunan yang betul.
Contoh pelaksanaan
Pelaksanaan khusus sebahagian besarnya bergantung pada bahasa pengaturcaraan yang digunakan, sintaks dan strukturnya.
Pelaksanaan C klasik menggunakan pembolehubah sementara untuk menukar nilai:
int i, j, temp; untuk (i=1; i =0; j--) { if (array[j] < temp) break; tatasusunan[j + 1]=tatasusunan[j]; tatasusunan[j]=temp; } }
Pelaksanaan PHP:
fungsi sisipan_sort(&$a) { untuk ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Di sini, pertama sekali, semua elemen yang tidak sepadan dengan keadaan isihan dianjak ke kanan, dan kemudian elemen semasa dimasukkan ke dalam ruang kosong.
Kod Java menggunakan gelung while:
sisipan lompang statik awamSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Maksud umum kod kekal tidak berubah: setiap elemen tatasusunan secara berurutan dibandingkan dengan yang sebelumnya dan ditukar dengannya jika perlu.
Anggaran masa berjalan
Jelas sekali, dalam kes terbaik, input algoritma akan menjadi tatasusunan yang telah dipesan dengan cara yang betul. Dalam keadaan ini, algoritma hanya perlu menyemak setiap elemen untuk memastikan ia berada di tempat yang betul tanpa membuat pertukaran. Oleh itu, masa berjalan akan bergantung secara langsung pada panjang tatasusunan asal O(n).
Input kes terburuk ialah tatasusunan yang diisih dalam susunan terbalik. Ini memerlukan sebilangan besar pilih atur, fungsi masa jalan bergantung pada bilangan elemen kuasa dua.
Bilangan pilih atur yang tepat untuk tatasusunan yang tidak tertib sepenuhnya boleh dikira menggunakan formula:
n(n-1)/2
dengan n ialah panjang tatasusunan asal. Oleh itu, ia akan mengambil 4950 pilih atur untuk menyusun 100 elemen dalam susunan yang betul.
Kaedah sisipan sangat cekap untuk mengisih tatasusunan kecil atau sebahagiannya. Walau bagaimanapun, ia tidak disyorkan untuk digunakan di mana-mana sahaja kerana kerumitan pengiraan yang tinggi.
Algoritma digunakan sebagai tambahan dalam banyak kaedah pengisihan lain yang lebih kompleks.
Isih nilai yang sama
Algoritma sisipan tergolong dalam jenis yang dipanggil stabil. Ia bermaksud,bahawa ia tidak menukar unsur yang sama, tetapi mengekalkan susunan asalnya. Indeks kestabilan dalam banyak kes penting untuk susunan yang betul.
Di atas ialah contoh visual yang bagus bagi isihan sisipan dalam tarian.
