Quicksort
Bagi dan taklukkan.
Quicksort adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Bagi dan Taklukkan
Quicksort adalah algoritma pengurutan dengan strategi bagi dan taklukkan. Algoritma ini memilih sebuah poros, mempartisi larik agar elemen yang lebih kecil berada di kiri dan yang lebih besar di kanan, lalu mengurutkan kedua sisi secara rekursif.
Waktu rata-ratanya adalah O(n log n).
Langkah Partisi
Gagasan utamanya adalah partisi: menyusun ulang larik di sekitar poros sehingga semua elemen di sebelah kiri poros lebih kecil dan semua elemen di sebelah kanannya lebih besar. Poros kemudian berada di posisi akhirnya dalam urutan.
Skema Partisi Lomuto
Skema Lomuto menggunakan elemen terakhir sebagai poros. Skema ini menyimpan indeks i sebagai batas elemen yang lebih kecil dan melakukan pertukaran saat menelusuri larik.
#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;
}Pengurutan Rekursif
Quicksort memanggil partisi, lalu melakukan rekursi pada dua sublarik di sekitar poros. Kasus dasarnya adalah sublarik berukuran 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 Poros yang Baik
Poros yang buruk (misalnya selalu memilih elemen terakhir pada masukan terurut) menyebabkan perilaku O(n kuadrat). Pilihan yang lebih baik menyebarkan partisi secara lebih merata.
- Median dari tiga
- Poros acak
Median dari Tiga
Median dari tiga memilih nilai tengah dari elemen pertama, tengah, dan terakhir sebagai poros, sehingga menghindari perilaku kasus terburuk pada data yang sudah terurut.
#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 Kasus Terburuk
Jika setiap partisi hanya memisahkan satu elemen, kedalaman rekursi menjadi n dan biayanya adalah O(n kuadrat). Hal ini terjadi ketika poros tetap digunakan pada masukan yang terurut atau terurut terbalik.
Pengacakan membuat kasus terburuk sangat tidak mungkin terjadi.
Poros Acak
Menukar elemen acak ke posisi poros sebelum melakukan partisi melindungi algoritma dari masukan yang dirancang untuk menghasilkan kinerja buruk.
#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;
}Di Tempat dan Tidak Stabil
Quicksort mengurutkan di tempat dengan hanya menggunakan ruang tumpukan O(log n) secara rata-rata. Namun, algoritma ini tidak stabil: elemen yang sama dapat berubah urutannya akibat pertukaran saat partisi.
Optimasi Pemanggilan Ekor
Melakukan rekursi terlebih dahulu pada bagian yang lebih kecil dan menggunakan perulangan pada bagian yang lebih besar membatasi kedalaman tumpukan hingga O(log n), sehingga mencegah tumpukan meluap pada larik besar.
Mengurutkan String
Struktur yang sama dapat mengurutkan jenis data apa pun yang dapat dibandingkan. Di sini quicksort mengurutkan larik bilangan bulat, tetapi mengganti perbandingannya juga dapat menangani jenis data 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;
}Pemeriksaan Singkat
Uji pemahaman Anda tentang quicksort.
Ringkasan
Anda telah mempelajari quicksort.
- Partisikan di sekitar poros, lalu lakukan rekursi pada setiap sisi
- Rata-rata O(n log n), kasus terburuk O(n kuadrat)
- Poros median dari tiga atau poros acak menghindari kasus terburuk
- Bekerja di tempat, tetapi tidak stabil
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Quicksort” gratis?
Ya — teks lengkap “Quicksort” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Quicksort”?
Bagi dan taklukkan. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Quicksort” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.