pengantar
Menyortir array adalah salah satu masalah serius pertama yang dipelajari dalam kursus klasik "Algoritma dan Struktur Data" dari disiplin ilmu komputer. Dalam hal ini, tugas menyortir menulis dan pertanyaan terkait sering ditemui dalam wawancara untuk posisi magang atau pengembang junior.
Rumusan masalah
Secara tradisional, ada baiknya memulai presentasi solusi untuk masalah dengan pernyataannya. Biasanya tugas pengurutan melibatkan pengurutan beberapa larik bilangan bulat dalam urutan menaik. Namun kenyataannya, ini agak terlalu menyederhanakan. Algoritme yang dijelaskan di bagian ini dapat digunakan untuk mengurutkan larik objek apa pun di mana relasi keteraturan dibuat (yaitu, untuk dua elemen apa pun, kita dapat mengatakan: yang pertama lebih besar dari yang kedua, yang kedua lebih besar dari yang pertama, atau keduanya sama). Anda dapat mengurutkan dalam urutan naik dan turun. Kami akan menggunakan penyederhanaan standar.
Urutan cepat
Terakhir kali kita berbicara tentang sortir yang sedikit lebih rumit - semacam penyisipan. Hari ini kita akan berbicara tentang algoritma yang jauh lebih kompleks - pengurutan cepat (juga disebut pengurutan Hoare).
Deskripsi Algoritma
Algoritma pengurutan cepat bersifat rekursif, oleh karena itu, untuk kesederhanaan, prosedur akan mengambil sebagai masukan batas segmen array dari l inklusif hingga r tidak inklusif. Jelas bahwa untuk mengurutkan seluruh larik, Anda harus meneruskan 0 sebagai parameter l, dan n sebagai r, di mana, menurut tradisi, n menunjukkan panjang larik.
Algoritma quicksort didasarkan pada prosedur partisi. Partisi memilih beberapa elemen dari array dan mengatur ulang elemen-elemen dari bagian array sehingga array tersebut dipecah menjadi 2 bagian: bagian kiri berisi elemen yang lebih kecil dari elemen ini, dan bagian kanan berisi elemen yang lebih besar atau sama dengan elemen ini. Elemen pemisah ini disebut poros .
Implementasi partisi:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
Pivot dalam kasus kami dipilih secara acak. Algoritma ini disebut acak . Faktanya, pivot dapat dipilih dengan berbagai cara: mengambil elemen acak, atau mengambil elemen pertama / terakhir dari bagian, atau memilihnya dengan cara "cerdas". Pilihan pivot sangat penting untuk kompleksitas akhir dari algoritme pengurutan, tetapi lebih dari itu nanti. Kompleksitas prosedur partisi adalah O (n), di mana n = r - l adalah panjang bagiannya.
Sekarang kami menggunakan partisi untuk mengimplementasikan pengurutan:
Implementasi partisi:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
Kasus ekstrem - larik satu elemen memiliki properti terurut. Jika arraynya panjang, maka kita menggunakan partisi dan memanggil prosedur secara rekursif pada dua bagian dari array.
Jika Anda menjalankan pengurutan tertulis menggunakan contoh larik 1 2 2, Anda akan melihat bahwa ini tidak akan pernah berakhir. Kenapa ini terjadi?
Saat menulis partisi, kami membuat asumsi - semua elemen array harus unik. Jika tidak, nilai kembalian dari m akan menjadi l dan rekursi tidak akan pernah berakhir, karena sort (l, m) akan memanggil sort (l, l) dan sort (l, m). Untuk mengatasi masalah ini, Anda perlu membagi array bukan menjadi 2 bagian (<pivot dan> = pivot), tetapi menjadi 3 bagian (<pivot, = pivot,> pivot) dan memanggil pengurutan rekursif untuk bagian 1 dan 3.
Analisis
Saya mengusulkan untuk menganalisis algoritma ini.
Kompleksitas waktu dari algoritme diekspresikan melalui rumus: T (n) = n + T (a * n) + T ((1 - a) * n). Jadi, ketika kita memanggil pengurutan sebuah array dari n elemen, dibutuhkan sekitar n operasi untuk mengeksekusi partisi dan mengeksekusi dirinya sendiri 2 kali dengan parameter a * n dan (1 - a) * n, karena pivot membagi elemen menjadi pecahan.
Dalam kasus terbaik, a = 1/2, yaitu, poros membagi area menjadi dua bagian yang sama setiap saat. Dalam hal ini: T (n) = n + 2 * T (n / 2) = n + 2 * (n / 2 + 2 * T (n / 4)) = n + n + 4 * T (n / 4 ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. Total akan menjadi log (n) suku, karena suku-suku tersebut muncul hingga argumen berkurang menjadi 1. Hasilnya, T (n) = O (n * log (n)).
Dalam kasus terburuk, a = 1 / n, yaitu, pivot memotong tepat satu elemen. Bagian pertama dari array berisi 1 elemen, dan yang kedua berisi n - 1. Yaitu: T (n) = n + T (1) + T (n - 1) = n + O (1) + T (n - 1) = n + O (1) + (n - 1 + O (1) + T (n - 2)) = O (n ^ 2). Kotak muncul karena fakta bahwa itu muncul dalam rumus untuk jumlah perkembangan aritmatika yang muncul dalam proses menulis rumus.
Rata-rata, idealnya, ekspektasi matematis dari berbagai pilihan harus dipertimbangkan. Dapat ditunjukkan bahwa jika pivot membagi larik dengan rasio 1: 9, maka asimtotik yang dihasilkan akan tetap O (n * log (n)).
Penyortiran disebut cepat, karena konstanta yang tersembunyi di bawah tanda O ternyata cukup kecil dalam praktiknya, yang menyebabkan penggunaan algoritme dalam praktik meluas.
Baca lebih banyak
