Mergesort
Kararlı sıralama
Mergesort, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 3. 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.
Kararlı Sıralama
Birleştirmeli sıralama, diziyi ikiye bölen, her yarıyı sıralayan ve ardından onları yeniden birleştiren böl ve yönet sıralamasıdır. Her durumda O(n log n) zaman karmaşıklığına sahiptir ve kararlıdır.
Bölme Adımı
Diziyi, her parçada tek bir öğe kalana kadar orta noktadan özyinelemeli olarak bölün. Tek bir öğe doğal olarak sıralıdır; bu, temel durumdur.
Birleştirme Adımı
Temel işlem, önceden sıralanmış iki diziyi tek bir dizi hâline getirir. Her ikisini de dizin işaretçileriyle tarayın ve her seferinde öndeki küçük öğeyi kopyalayın.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Neden Kararlıdır
Birleştirme işleminde a[i] <= a[j] kullanılır; bu nedenle iki öğe eşit olduğunda önce soldaki diziden olan alınır. Sol dizi daha önceki öğeleri içerdiğinden, özgün sıra korunur.
Özyinelemeli Sürücü
Birleştirmeli sıralama her yarı üzerinde özyinelemeli olarak çalışır, ardından yarıları birleştirir. Her çağrıda yeni bellek ayırmaktan kaçınmak için ortak bir geçici arabellek iletiriz.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Bellek Kullanımı
Hızlı sıralamanın aksine, birleştirmeli sıralama birleştirme arabelleği için O(n) ek bellek gerektirir. Bu, belleğin kısıtlı olduğu durumlarda çok büyük diziler için temel dezavantajıdır.
Garantili O(n log n)
Özyineleme her zaman diziyi ikiye böler; böylece log n düzey oluşur ve her düzeyde n öğe birleştirilir. Bu nedenle birleştirmeli sıralama, hızlı sıralamanın aksine en iyi, ortalama ve en kötü durumların tümünde O(n log n) olur.
Birleştirme Düzeylerini Sayma
Özyineleme düzeylerinin sayısı ceil(log2 n) değeridir. Bunu birkaç boyut için hesaplayalım.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Aşağıdan Yukarıya Birleştirmeli Sıralama
Yinelemeli bir çeşidi, önce 1, sonra 2, ardından 4 boyutundaki dizileri birleştirir ve her geçişte boyutu iki katına çıkarır. Özyinelemeyi tamamen ortadan kaldırır ve bağlı listeler için uygundur.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Birleştirmeli Sıralama Ne Zaman Seçilmelidir
Şunlara ihtiyaç duyduğunuzda birleştirmeli sıralamayı tercih edin:
- Kötü durumları olmayan, garantili O(n log n)
- Kararlılık
- Bağlı listeleri sıralama (rastgele erişim gerekmez)
- RAM'e sığmayacak kadar büyük veriler için harici sıralama
Birleştirmeli Sıralama ve Hızlı Sıralama
Hızlı sıralama uygulamada genellikle daha hızlıdır ve yerinde sıralama yapar; ancak en kötü durumu kötü olduğunda kararlı değildir. Birleştirmeli sıralama garantili bir sınıra sahip ve kararlıdır, fakat ek bellek kullanır. Seçiminizi kısıtlarınıza göre yapın.
Hızlı Kontrol
Birleştirmeli sıralamayı ne kadar anladığınızı test edin.
Özet
Birleştirmeli sıralamayı öğrendiniz.
- İkiye bölün, her parçayı sıralayın, ardından birleştirin
- Birleştirme, eşit anahtarlarda solu önce tutarak kararlılık sağlar
- Tüm durumlarda garantili O(n log n)
- O(n) ek bellek kullanır; bağlı listeler ve harici sıralamalar için idealdir
Sıkça Sorulan Sorular
“Mergesort” dersi ücretsiz mi?
Evet — “Mergesort” 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.
“Mergesort” dersinde ne öğreneceğim?
Kararlı sıralama 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 3. dersidir.
“Mergesort” 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.