Quicksort
Böl ve yönet
Quicksort, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.
Böl ve Yönet
Quicksort, böl ve yönet yaklaşımını kullanan bir sıralamadır. Bir pivot seçer, küçük öğeler sola ve büyük öğeler sağa gidecek şekilde diziyi böler, ardından her iki tarafı özyinelemeli olarak sıralar.
Ortalama çalışma süresi O(n log n)'dir.
Bölümleme Adımı
Temel fikir bölümlemedir: diziyi bir pivot çevresinde yeniden düzenleyerek pivotun solundaki her şeyin daha küçük, sağındaki her şeyin daha büyük olmasını sağlamak. Böylece pivot, sıralanmış nihai konumuna yerleşir.
Lomuto Bölümleme Şeması
Lomuto şeması son öğeyi pivot olarak kullanır. Küçük öğelerin sınırı için i dizinini tutar ve tarama sırasında yer değiştirme yapar.
#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;
}Özyinelemeli Sıralama
Quicksort, bölümleme işlemini çağırır; ardından pivotun çevresindeki iki alt dizide özyinelemeli olarak çalışır. Temel durum, boyutu 0 veya 1 olan bir alt dizidir.
#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;
}İyi Bir Pivot Seçme
Kötü bir pivot (örneğin sıralı girdide her zaman son öğeyi seçmek) O(n kare) davranışına yol açar. Daha iyi seçimler bölümleri daha dengeli dağıtır.
- Üçlü medyan
- Rastgele pivot
Üçlü Medyan
Üçlü medyan, ilk, orta ve son öğelerin medyanını pivot olarak seçer ve zaten sıralı verilerdeki en kötü durum davranışını önler.
#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;
}En Kötü Durum Analizi
Her bölümlemede yalnızca bir öğe ayrılırsa özyineleme derinliği n olur ve maliyet O(n kare)'ye çıkar. Bu durum, sıralı veya ters sıralı girdide sabit bir pivot kullanıldığında gerçekleşir.
Rastgeleleştirme, en kötü durumun gerçekleşme olasılığını son derece düşürür.
Rastgele Pivot
Bölümlemeden önce rastgele bir öğeyi pivot konumuna taşımak, kötü niyetle hazırlanmış girdilere karşı koruma sağlar.
#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;
}Yerinde ve Kararlı Değil
Quicksort, ortalama durumda yalnızca O(log n) yığın alanı kullanarak yerinde sıralama yapar. Ancak kararlı değildir: eşit öğelerin sırası, bölümleme sırasında yapılan yer değiştirmelerle değişebilir.
Kuyruk Çağrısı İyileştirmesi
Önce küçük yarıda özyinelemeli olarak çalışıp büyük yarıda döngü kullanmak, yığın derinliğini O(log n) ile sınırlar ve büyük dizilerde yığın taşmasını önler.
Dizeleri Sıralama
Aynı yapı, karşılaştırılabilir her türü sıralayabilir. Burada quicksort bir tamsayı dizisini sıralıyor; karşılaştırmayı değiştirdiğinizde diğer türleri de sıralayabilirsiniz.
#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;
}Kısa Kontrol
Quicksort hakkındaki anlayışınızı sınayın.
Özet
Quicksort'u öğrendiniz.
- Bir pivot çevresinde bölümleme yapın, ardından her iki tarafta özyinelemeli olarak çalışın
- Ortalama O(n log n), en kötü durumda O(n kare)
- Üçlü medyan veya rastgele pivotlar en kötü durumu önler
- Yerindedir ancak kararlı değildir
Sıkça Sorulan Sorular
“Quicksort” dersi ücretsiz mi?
Evet — “Quicksort” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.
“Quicksort” dersinde ne öğreneceğim?
Böl ve yönet C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
C Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Quicksort” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu C Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.