Sort Insert Langsung
Gagasan memasukkan penyortiran secara langsung mudah dimengerti, sepertinya ini:
1. Bagilah array yang akan diurutkan menjadi dua bagian: diurutkan dan tidak disortir. Pada awalnya, elemen pertama dianggap disortir.
2. Mulailah dengan elemen kedua, temukan posisi elemen yang sesuai di subarray yang diurutkan dan masukkan.
3. Ulangi proses di atas sampai elemen terakhir dimasukkan ke dalam subarray yang dipesan.
4. Penyortiran selesai.
Contoh:
Idenya sederhana, tetapi kodenya tidak semudah ditulis sebagai penyortiran gelembung. Pertama -tama, bagaimana menentukan posisi yang tepat? Lebih besar dari atau sama dengan kiri, kurang dari atau sama dengan kanan? Tidak, banyak kondisi batas perlu dipertimbangkan, dan ada terlalu banyak penilaian. Kedua, memasukkan elemen ke dalam array pasti akan membutuhkan memindahkan sejumlah besar elemen. Bagaimana cara mengendalikan gerakan mereka?
Bahkan, ini bukan masalah dengan algoritma itu sendiri, dan ada hubungannya dengan bahasa pemrograman. Terkadang algoritma itu sendiri sudah sangat matang, dan masih perlu sedikit berubah ketika datang ke bahasa pemrograman tertentu. Apa yang kita bicarakan di sini adalah algoritma Java, jadi mari kita bicara tentang Java.
Untuk menyelesaikan masalah di atas, kami telah melakukan sedikit penyempurnaan dari langkah kedua. Kami tidak memulai perbandingan dari posisi awal sub-array, tetapi mulai perbandingan terbalik dari ekor sub-array. Selama lebih besar dari angka yang perlu dimasukkan, kami bergerak mundur. Sampai angka tidak lebih besar dari angka, maka angka yang akan dimasukkan akan ditempatkan pada posisi kosong ini. Karena itu, kita dapat menulis kode berikut:
InsertArray.java
kelas publik insertArray {// array private long [] arr; // ukuran data yang valid dalam array private int elem; // Konstruktor default InsertArArray () {arr = new Long [50]; } public insertArray (int max) {arr = new Long [max]; } // masukkan data public void insert (nilai panjang) {arr [elems] = value; elem ++; } // Tampilkan data public void display () {for (int i = 0; i <elems; i ++) {System.out.print (arr [i]+""); } System.out.println (); } // masukkan sortir public void sisipan () {long select = 0l; untuk (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; untuk (j = i; j> 0 && arr [j - 1]> = select; j--) {arr [j] = arr [j - 1]; } arr [j] = pilih; }}} Kelas Tes:
Testinserarray.java
TestIserRay kelas publik {public static void main (string [] args) {insertArray iarr = new insertArray (); iarr.insert (85); iarr.insert (7856); iarr.insert (12); iarr.insert (8); iarr.insert (5); iarr.insert (56); iarr.display (); iarr.insertsort (); iarr.display (); }} Hasil Cetak:
Kinerja/kompleksitas algoritma
Sekarang mari kita bahas kompleksitas waktu dari algoritma penyisipan langsung. Terlepas dari inputnya, algoritma selalu melakukan putaran penyortiran N-1. Namun, karena titik penyisipan setiap elemen tidak pasti dan sangat dipengaruhi oleh data input, kompleksitasnya tidak pasti. Kita dapat membahas situasi terbaik, terburuk dan rata -rata.
1. Kasus Terbaik: Dari karakteristik algoritma, dapat dilihat bahwa ketika array yang akan diatur sendiri dalam urutan positif (array dipesan dan urutannya sama dengan urutan yang diperlukan, yang dalam urutan naik di bawah premis diskusi kami). Alasannya adalah bahwa dalam hal ini, setiap elemen hanya perlu dibandingkan sekali dan tidak perlu dipindahkan. Kompleksitas waktu algoritma adalah O (n);
2. Kasus terburuk: Jelas, ketika array yang akan diatur dalam urutan terbalik, itu adalah kasus terburuk. Dalam hal ini, jumlah perbandingan kami per putaran adalah I-1 dan jumlah penugasan adalah i. Jumlah total kali adalah jumlah dari istilah n pertama dari seri 2n-1, yaitu, n^2. Kompleksitas waktu algoritma adalah O (n^2);
3. Situasi Rata -rata: Dari analisis di atas, kita dapat memperoleh bahwa jumlah operasi algoritma dalam situasi rata -rata kira -kira (n^2)/2 (Catatan: Perhitungan di sini didasarkan pada penugasan dan perbandingan. Jika didasarkan pada gerakan dan perbandingan, kira -kira n^2/4). Jelas, kompleksitas waktu masih O (n^2).
Adapun kompleksitas spasial algoritma, semua gerakan dilakukan di dalam data. Satu -satunya overhead adalah bahwa kami memperkenalkan variabel sementara (beberapa struktur data disebut "sentinel" dalam buku), sehingga kompleksitas spasialnya (ruang ekstra) adalah O (1).
Stabilitas algoritma
Karena Anda hanya perlu menemukan posisi yang tidak lebih besar dari angka saat ini dan tidak perlu bertukar, memasukkan sortir secara langsung adalah metode penyortiran yang stabil.
Varian Algoritma
Jika ada banyak data yang harus diatur, maka itu akan menyebabkan banyak overhead setiap kali Anda melihat dari belakang ke depan. Untuk meningkatkan kecepatan pencarian, pencarian biner dapat digunakan untuk optimasi kinerja. Karena efisiensi pencarian biner sangat tinggi, kompleksitas O (n) dipastikan, dan efisiensi pencarian dapat sangat ditingkatkan ketika ada lebih banyak data atau data input cenderung paling buruk. Dalam beberapa buku, metode ini disebut lipat dan setengah penyortiran. Implementasinya cukup rumit dan dapat diposting jika Anda punya waktu di masa depan.
Selain itu, ada jenis insert 2 arah dan jenis insert tabel. Sortir penyisipan 2 arah semakin ditingkatkan berdasarkan lipat dan setengah penyisipan, dan jumlah gerakannya sangat berkurang, sekitar n^2/8. Namun, itu tidak menghindari jumlah gerakan dan tidak mengurangi tingkat kompleksitas. Penyisipan tabel benar -benar mengubah struktur penyimpanan dan tidak memindahkan catatan, tetapi daftar yang ditautkan perlu dipertahankan, dan penunjuk daftar tertaut dimodifikasi alih -alih memindahkan catatan. Oleh karena itu, kompleksitasnya masih o (n^2).
Untuk pemasangan penyisipan 2 arah dan penyisipan tabel, Anda dapat merujuk pada buku "Struktur Data" yang diedit oleh Yan Weimin dan Wu Weimin.
Algoritma skenario yang berlaku
Penyortiran penyisipan tidak berlaku ketika array besar karena kompleksitas O (n^2). Namun, ketika ada data yang relatif sedikit, itu adalah pilihan yang baik, umumnya digunakan sebagai ekspansi untuk penyortiran cepat. Misalnya, dalam algoritma STL STL dan algoritma QSORT STDLIB, masukkan penyortiran digunakan sebagai suplemen untuk penyortiran cepat dan digunakan untuk mengurutkan sejumlah kecil elemen. Misalnya, dalam implementasi metode pengurutan yang digunakan dalam JDK 7 java.util.arrays, ketika panjang array yang akan diurutkan kurang dari 47, masukkan penyortiran akan digunakan.