Sortir menurut sisipan

Halo. Hari ini kami melanjutkan serangkaian artikel yang saya tulis khusus untuk peluncuran kursus "Algoritma dan Struktur Data" dari OTUS.

---

pengantar

Menyortir sebuah array adalah salah satu masalah serius pertama yang dipelajari dalam kursus klasik "Algoritma dan Struktur Data" dari disiplin ilmu komputer. Dalam hal ini, tugas menulis macam-macam dan pertanyaan yang sesuai sering ditemui dalam wawancara sebagai pengembang magang atau junior.

Perumusan masalah

Secara tradisional, ada baiknya memulai presentasi solusi untuk masalah dengan pernyataannya. Biasanya tugas menyortir melibatkan memesan beberapa bilangan bulat dalam urutan naik. Tetapi pada kenyataannya, ini agak terlalu disederhanakan. Algoritme yang dijelaskan dalam bagian ini dapat digunakan untuk memesan array dari objek apa pun di mana hubungan pemesanan dibuat (yaitu, untuk dua elemen yang dapat kita katakan: yang pertama lebih besar dari yang kedua, yang kedua lebih besar dari yang pertama, atau mereka sama). Anda dapat mengurutkannya dalam urutan naik dan turun. Kami akan menggunakan penyederhanaan standar.

Sortir menurut sisipan

Terakhir kali kami berbicara tentang salah satu yang paling sederhana - pemilihan . Hari ini kita akan fokus pada algoritma yang sedikit lebih kompleks - jenis penyisipan.

Deskripsi Algoritma

Mengurutkan array dengan menyisipkan dilakukan dengan cara berikut: seperti halnya dalam kasus pemilihan, array dibagi menjadi dua bagian. Satu bagian disebut diurutkan dan yang lainnya tidak disortir. Algoritma ini mengasumsikan melintasi seluruh array sehingga panjang bagian yang diurutkan menjadi sama dengan panjang seluruh array. Dalam setiap iterasi, kami mengambil elemen pertama dari bagian array yang tidak disortir dan melakukan operasi berikut dengan itu: sementara elemen kami benar-benar kurang dari yang sebelumnya, kami menukar mereka. Kemudian kita menambah panjang bagian array yang diurutkan berdasarkan satu. Jadi, dengan memindahkan elemen yang sedang dipelajari secara berurutan, kami mencapai bahwa elemen tersebut jatuh ke tempatnya. Contoh satu iterasi disajikan di bawah ini:

1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Penerapan

Saya sarankan melihat implementasi algoritma ini di C:

void insertionSortFunction(double array[], int size) {
    int i, j, temp;
    // i     ,   1,         
    for (i = 1; i < size; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < temp) {
                break;
            }
  
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}

Analisis

Saya mengusulkan untuk menganalisis algoritma ini.



Cara termudah untuk memulai analisis adalah mendapatkan asimtotik memori. Terlepas dari panjang dan struktur array yang diusulkan untuk disortir, memori hanya dialokasikan untuk dua counter loop dan satu variabel tambahan yang digunakan untuk bertukar dua nilai variabel. Jadi, selalu benar:

$$

$$M(n) = O(1)$$

...



Seiring waktu, semuanya agak lebih menarik. Tubuh loop dalam itu sendiri membutuhkan O (1), yaitu, itu tidak tergantung pada ukuran array yang diurutkan. Ini berarti bahwa untuk memahami asimtotik dari algoritma, perlu untuk menghitung berapa kali tubuh ini dieksekusi. Tetapi jumlah iterasi loop dalam tergantung pada seberapa baik memesan (atau tidak berurutan) elemen-elemen array yang diurutkan. Beberapa kasus perlu dilihat untuk dianalisis.



Jumlah minimum iterasi tercapai jika array yang akan diurutkan sudah diurutkan. Memang, untuk setiap iterasi dari luar untuk loop, tepat satu iterasi dari loop dalam terjadi. Inilah yang disebut kasus terbaik .

$$

$$T(n) = (n - 1) * O(1) = O(n)$$

Jadi, penyortiran dilakukan dalam waktu linier.



Dalam kasus terburuk, jumlah iterasi diasumsikan sebagai yang terbesar, yaitu, break tidak pernah terjadi kebakaran. Pada iterasi pertama dari loop luar, satu iterasi dari loop dalam dilakukan. Pada iterasi kedua dari loop luar, 2 iterasi dari loop dalam dilakukan. Melanjutkan penalaran lebih lanjut, kita dapat sampai pada kesimpulan bahwa pada iterasi terakhir (n - 1) - th) dari loop luar (n - 1) iterasi dari loop dalam akan dieksekusi. Kita mendapatkan:

$$

$$T(n) = O(1) + 2 * O(1) + 3 * O(1) + ... + (n - 1) * O(1) = O(1 + 2 + 3 + ... + (n - 1)) = O(n * (n - 1) / 2) = O(n ^ 2)$$

Untuk melakukan perhitungan, kami menggunakan properti notasi O dan rumus untuk jumlah perkembangan aritmatika.



Dalam kasus rata - rata, diasumsikan bahwa jumlah iterasi loop dalam untuk iterasi tertentu dari loop luar sama dengan nilai rata-rata, yaitu, ekspektasi matematis. Misalkan semua angka yang diperbolehkan dari tembakan loop dalam kemungkinan sama. Dalam hal ini, jumlah rata-rata iterasi loop dalam adalah . Saya diasumsikan sebagai nomor iterasi dari loop luar. Sekarang, untuk menghitung asimptotik, Anda perlu menghitung . Artinya, kita hanya menghitung berapa kali tubuh loop dalam dieksekusi. Jadi, kita dapatkan .



Untuk meringkas, memori asimtotik dari algoritma ini adalah

$$

$$O(1)$$

tepat waktu

$$

$$O(n)$$

dan rata-rata dan kasus terburuk

$$

$$O(n^2)$$

Oleh karena itu, penyortiran ini milik kelas macam kuadrat .



Penting juga untuk dicatat bahwa pemilihan sortir kuat dalam implementasi ini . Biarkan saya mengingatkan Anda bahwa penyortiran disebut stabil jika urutan elemen yang sama tidak berubah selama pelaksanaannya. Properti ini tidak terlalu penting untuk tugas pendidikan seperti menyortir array angka, tetapi jika kami menyortir beberapa objek yang lebih kompleks dengan relasi pemesanan yang mapan, mungkin penting. Kita dapat mempertimbangkan contoh serupa kapan kita berbicara tentang penyortiran radix.

Hasil

Kami melihat jenis kuadrat lain: jenis penyisipan, melihat penerapannya yang kuat. Penyortiran sebagian besar bersifat mendidik, meskipun dalam praktiknya hal itu dapat diterapkan karena asimptotik yang baik paling baik: jika Anda perlu menambahkan data baru ke jumlah data yang cukup besar sehingga semua data dipesan lagi, bagian dalam untuk loop dapat berguna. Sehingga bisa didukung untuk

$$

$$O(n)$$

keteraturan volume data.

---

Pelajari lebih lanjut tentang kursus.

---