Quicksort
Bahagi dan takluk
Quicksort ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.
Bahagi dan Takluk
Pengisihan pantas ialah pengisihan bahagi dan takluk. Ia memilih pangsi, membahagikan tatasusunan supaya unsur yang lebih kecil berada di kiri dan yang lebih besar di kanan, kemudian mengisih setiap bahagian secara rekursif.
Masa purata ialah O(n log n).
Langkah Pembahagian
Idea utamanya ialah pembahagian: susun semula tatasusunan di sekitar pangsi supaya segala-galanya di sebelah kiri pangsi lebih kecil dan segala-galanya di sebelah kanan lebih besar. Pangsi kemudiannya berada pada kedudukan akhirnya yang telah diisih.
Skim Pembahagian Lomuto
Skim Lomuto menggunakan unsur terakhir sebagai pangsi. Ia mengekalkan indeks i sebagai sempadan unsur yang lebih kecil dan melakukan pertukaran semasa mengimbas.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Pengisihan Rekursif
Pengisihan pantas memanggil pembahagian, kemudian berulang secara rekursif pada dua sub-tatasusunan di sekeliling pangsi. Kes asas ialah sub-tatasusunan bersaiz 0 atau 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Memilih Pangsi yang Baik
Pangsi yang buruk (seperti sentiasa memilih unsur terakhir pada input yang telah diisih) menyebabkan tingkah laku O(n kuasa dua). Pilihan yang lebih baik membahagikan tatasusunan dengan lebih seimbang.
- Median tiga
- Pangsi rawak
Median Tiga
Median tiga memilih median daripada unsur pertama, tengah dan terakhir sebagai pangsi, sekali gus mengelakkan tingkah laku kes terburuk pada data yang telah diisih.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Analisis Kes Terburuk
Jika setiap pembahagian hanya memisahkan satu unsur, kedalaman rekursi menjadi n dan kosnya ialah O(n kuasa dua). Ini berlaku dengan pangsi tetap pada input yang telah diisih atau diisih secara terbalik.
Pengrawakan menjadikan kes terburuk amat tidak mungkin berlaku.
Pangsi Rawak
Menukar unsur rawak ke kedudukan pangsi sebelum pembahagian melindungi daripada input yang direka untuk menjejaskan prestasi.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}Dalam Tempat dan Tidak Stabil
Pengisihan pantas mengisih di tempat dengan hanya menggunakan ruang tindanan O(log n) secara purata. Walau bagaimanapun, ia tidak stabil: unsur yang sama mungkin disusun semula oleh pertukaran semasa pembahagian.
Pengoptimuman Panggilan Ekor
Melakukan rekursi pada separuh yang lebih kecil dahulu dan menggunakan gelung pada separuh yang lebih besar mengehadkan kedalaman tindanan kepada O(log n), lalu mengelakkan limpahan tindanan pada tatasusunan besar.
Mengisih Rentetan
Struktur yang sama boleh mengisih sebarang jenis yang boleh dibandingkan. Di sini pengisihan pantas menyusun tatasusunan integer, tetapi menukar perbandingan membolehkannya mengendalikan jenis lain.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Semakan Pantas
Uji pemahaman anda tentang pengisihan pantas.
Imbas Kembali
Anda telah mempelajari pengisihan pantas.
- Bahagikan di sekitar pangsi, kemudian lakukan rekursi pada setiap bahagian
- Purata O(n log n), kes terburuk O(n kuasa dua)
- Pangsi median tiga atau pangsi rawak mengelakkan kes terburuk
- Dilakukan di tempat tetapi tidak stabil
Pelajari C dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 39
- Pelajaran
- 144
Soalan Lazim
Adakah pelajaran “Quicksort” percuma?
Ya — teks penuh “Quicksort” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Quicksort”?
Bahagi dan takluk Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan C Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Quicksort” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.