Kompleksitas waktu
Rata -rata: o (nlgn)
Kasus terburuk: o (n*n), terjadi ketika data sudah dalam keadaan penyortiran.
1. Pilih nilai A [i] dari data sebagai referensi
2. Mengambil [i] sebagai referensi, bagi data menjadi 2 bagian: P1 dan P2. Semua data dalam p1≤a [i], semua data dalam p2> a [i], dan data menjadi {{p1} {a [i]} {p2}}
3. Ulangi langkah -langkah di atas dengan P1 dan P2 sampai hanya 1 data yang tersisa di setiap bagian.
4. Data diurutkan dalam urutan naik
Contoh Dasar:
Data mentah:
{3, 9, 8, 5, 2, 1, 6} Langkah 1: Pilih data pertama: 3
Langkah 2: Bagilah data menjadi 2 bagian, sisi kiri adalah ≤3, dan sisi kanan lebih besar dari> 3:
{2,1} {3} {9,8,5,6} Langkah 3: Ulangi langkah -langkah di atas untuk setiap bagian sampai hanya ada 1 data yang tersisa di setiap bagian:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9} Langkah 4: Data diurutkan dalam urutan naik:
{1} {2} {3} {5} {6} {8} {9}Data dalam program biasanya disimpan dalam array. Mengambil array tipe int sebagai contoh, Anda dapat menulis langkah -langkah di atas ke prototipe fungsi quicksort:
quicksort (int begin, int end) {// begin adalah nilai indeks dari data pertama dari array, end adalah nilai indeks dari data terakhir dari array +1 // jika hanya ada 1 data atau 0 data, program pengembalian jika (begin == end || begin == (end-1)) pengembalian; int p = di [begin]; // p adalah data referensi yang dipilih, pilih data pertama int a = begin +1; //a as the index value of the 2-part data dividing line int b = a;//b is the index value of the data to be compared for( ; b < end; b++) {//Compare the data in the array with the reference data in sequence if( in[b] < p) { //If the data < reference data, move it to the left if(a == b){a++; Lanjutkan;} // Jika data sudah di sebelah kiri, itu tidak akan memindahkan int temp = di [a]; // pindahkan data ke kiri di [a] = di [b]; di [b] = temp; a ++; // pindahkan garis pemisah kanan}} di [begin] = di [a-1]; // Whoe nilai referensi ke tengah 2 set data dalam [a-1] = p; if (a-1> begin) {// Jika ada data di sebelah kiri, ulangi langkah-langkah di atas Quicksort (mulai, a); } if (end-1> a) {// Jika ada data di sebelah kanan, ulangi langkah-langkah di atas Quicksort (a, end); } kembali; // Jika tidak ada data} Optimalisasi Algoritma
Algoritma pengurut cepat di atas dapat dikatakan sebagai jenis cepat yang paling mendasar karena tidak memperhitungkan data input apa pun. Namun, mudah untuk menemukan kelemahan algoritma ini: ini adalah saat data input kami pada dasarnya dipesan atau bahkan sepenuhnya dipesan, algoritma merosot menjadi penyortiran gelembung, tidak lagi o (nn), tetapi o (n^2).
Akar penyebabnya adalah bahwa dalam implementasi kode kami, kami hanya mulai dari array pertama sekaligus. Jika kita menggunakan "tiga header", yaitu nilai median ARR [rendah], ARR [tinggi], arr [(rendah+tinggi)/2] sebagai catatan pivot, kinerja penyortiran cepat dalam skenario terburuk dapat sangat ditingkatkan. Namun, kami masih tidak dapat meningkatkan kinerjanya menjadi O (n) dalam kasus yang dipesan array. Ada juga cara untuk meningkatkan kinerja waktu penyortiran cepat dalam skenario terburuk hingga berbagai tingkat.
Selain itu, penyortiran cepat membutuhkan tumpukan rekursif, yang biasanya tidak terlalu dalam dan berada pada tingkat log (n). Namun, jika panjang dua array dibagi pada suatu waktu sangat tidak seimbang, dalam kasus terburuk, kedalaman tumpukan akan meningkat menjadi O (n). Pada saat ini, kompleksitas spasial yang dibawa oleh ruang tumpukan tidak dapat diabaikan. Jika overhead variabel tambahan ditambahkan, bahkan dapat mencapai kompleksitas ruang O (n^2) yang menakutkan di sini. Oleh karena itu, kompleksitas spasial terburuk dari penyortiran cepat bukanlah nilai tetap, dan bahkan mungkin tidak berada pada level yang sama.
Untuk mengatasi masalah ini, kita dapat membandingkan panjang ujungnya setelah setiap divisi dan mengurutkan urutan pendek terlebih dahulu (tujuannya adalah untuk mengakhiri tumpukan ini terlebih dahulu untuk membebaskan ruang), yang dapat mengurangi kedalaman maksimum kembali ke level O (n).
Berikut adalah tiga ide optimasi untuk penyortiran cepat:
Untuk susunan kecil, masukkan penyortiran dapat digunakan untuk menghindari panggilan rekursif. Misalnya, ketika (hai <= lo + m), Anda dapat menyisipkan sortir.
Gunakan median subarray untuk mengiris array. Ini menghasilkan pengiris yang lebih baik, tetapi dengan biaya menghitung median.
Jika array berisi sejumlah besar elemen berulang, pengiris tiga arah dapat digunakan. Bagilah array menjadi tiga bagian, sesuai dengan elemen array yang lebih kecil dari, sama dengan, dan masing -masing lebih besar dari mengiris elemen. Implementasi kode adalah sebagai berikut:
private static void sort1 (int [] a, int lo, int hi) {if (hai <= lo) kembali; int lt = lo, i = lo + 1, gt = hai; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } lain jika (a [i]> v) {swap (a, i, gt--); } else {i ++; } sort (a, lo, lt - 1); urutkan (a, gt + 1, hai); }}