Kabarcık ve Eklemeli Sıralama
Basit sıralamalar
Kabarcık ve Eklemeli Sıralama, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 1. 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.
Basit Sıralamalar
Kabarcık sıralaması ve eklemeli sıralama, karşılaştırmalı sıralamaların en basit ikisidir. Her ikisinin de en kötü durum maliyeti O(n kare)'dir; ancak anlaşılmaları kolaydır ve küçük ya da neredeyse sıralı diziler için kullanışlıdır.
Kabarcık Sıralaması Nasıl Çalışır
Kabarcık sıralaması diziyi tekrar tekrar dolaşarak sırası yanlış olan komşu çiftleri yer değiştirir. Her tam geçişten sonra kalan en büyük öğe yukarı çıkarak sondaki nihai konumuna yerleşir.
İki Tamsayıyı Yer Değiştirme
Yeniden kullanılabilir bir yer değiştirme yardımcısı, sıralama kodunun temiz kalmasını sağlar.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}Kabarcık Sıralaması Uygulaması
İç içe döngüler kullanılır: dış döngü geçişleri sayar, iç döngü komşu çiftleri karşılaştırıp yer değiştirir. i geçişinden sonra son i öğe sıralanmış olur.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Erken Çıkış İyileştirmesi
Tam bir geçişte hiç yer değiştirme yapılmazsa dizi zaten sıralıdır ve durabilirsiniz. Bu, kabarcık sıralamasının zaten sıralı girdide O(n) olmasını sağlar.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}Eklemeli Sıralama Nasıl Çalışır
Eklemeli sıralama, dizinin başında sıralı bir bölge oluşturur. Her yeni öğe için daha büyük sıralı öğeleri sağa kaydırır ve yeni öğeyi yerine yerleştirir; bu işlem eldeki iskambil kâğıtlarını sıralamaya benzer.
Eklemeli Sıralaması Uygulaması
key = a[i] öğesini alın; ardından a[0..i-1] içindeki her daha büyük öğeyi bir konum sağa kaydırın ve key öğesini oluşan aralığa ekleyin.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Neredeyse Sıralı Verilerde Eklemeli Sıralama
Eklemeli sıralama, dizi neredeyse sıralı olduğunda çok etkilidir: her öğe yalnızca birkaç konum ilerler ve maliyet O(n) değerine yaklaşır. Karma sıralamalarda sonlandırma adımı olarak kullanılmasının nedeni budur.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Kararlılık
Her iki sıralama da kararlıdır: eşit öğeler, yalnızca kesin büyük karşılaştırmasında yer değiştirdikleri veya kaydırıldıkları için ilk göreli sıralarını korur. Kayıtları birden çok anahtara göre sıralarken kararlılık önemlidir.
Karmaşıklık Karşılaştırması
Her ikisinin de ortalama ve en kötü durum maliyeti O(n kare)'dir; ancak pratikte farklıdırlar:
- Kabarcık: çok sayıda yer değiştirme yapar ve gerçek kodda nadiren kullanılır
- Eklemeli: daha az yazma işlemi yapar; küçük veya neredeyse sıralı diziler için çok uygundur
İyileştirmelerle her ikisinin en iyi durumu O(n)'dir.
İşlemleri Sayma
En kötü durum olan ters sıralı bir dizide eklemeli sıralamanın yaptığı karşılaştırmaları sayalım.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}Kısa Kontrol
Basit sıralamalar hakkındaki anlayışınızı sınayın.
Özet
O(n kare) maliyetli iki basit sıralama öğrendiniz.
- Kabarcık sıralaması her geçişte komşu çiftlerin yerini değiştirir
- Eklemeli sıralama, sıralı bölümün başına öğe kaydırıp ekler
- Her ikisi de kararlıdır; iyileştirmeyle sıralı girdide O(n) değerine ulaşır
- Küçük veriler için pratikte daha iyi seçim eklemeli sıralamadır
Sıkça Sorulan Sorular
“Kabarcık ve Eklemeli Sıralama” dersi ücretsiz mi?
Evet — “Kabarcık ve Eklemeli Sıralama” 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.
“Kabarcık ve Eklemeli Sıralama” dersinde ne öğreneceğim?
Basit sıralamalar 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 1. dersidir.
“Kabarcık ve Eklemeli Sıralama” 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.
Bu kursun tüm dersleri
- Kabarcık ve Eklemeli Sıralama
- Quicksort
- Mergesort
- qsort Kullanımı