Kabarcık Sıralaması ve Eklemeli Sıralama
Her iki karesel sıralama algoritmasını kodlayın, neden O(n²) olduklarını anlayın ve eklemeli sıralamanın birleştirmeli sıralamayı geçtiği tek durumu tanıyın.
Kabarcık Sıralaması ve Eklemeli Sıralama, CoddyKit'te ücretsiz bir DSA Interview Prep 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, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Neden O(n²) Sıralamalarını Öğrenmelisiniz?
Kabarcık sıralaması ve eklemeli sıralama, en kötü durumda O(n²) karmaşıklığındadır; bu da onları büyük girdiler için kullanışsız hâle getirir. Buna rağmen her ciddi algoritma mülakatında bunları uygulamanız ve analiz etmeniz beklenir. Bu algoritmalar, daha gelişmiş algoritmalara da uygulanan karşılaştırma, yer değiştirme, kararlı sıralama ve en iyi durum davranışı gibi temel kavramları öğretir. Mülakatçılar, döngü değişmezleri ve asimptotik gösterim hakkında ilkelerden hareketle akıl yürütüp yürütemediğinizi sınamak için bu algoritmaları kullanır.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Kabarcık Sıralaması: Maksimumu Yukarı Taşıma
Kabarcık sıralaması, diziyi tekrar tekrar tarar ve sırası yanlış olan komşu öğelerin yerini değiştirir. Her tam geçişten sonra sıralanmamış en büyük öğe "kabarcıklanarak" sondaki nihai konumuna çıkar. n-1 geçişten sonra dizinin tamamı sıralanmış olur. Adı, büyük öğelerin baloncuklar gibi yukarı doğru çıkmasından gelir. Açıklanması en kolay sıralama algoritmasıdır, ancak pratikte nadiren kullanılır.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Erken Çıkışlı Kabarcık Sıralaması
En iyi duruma getirilmiş kabarcık sıralaması bir swapped bayrağı kullanır: iç döngünün tam bir geçişinde hiç yer değiştirme yapılmazsa dizi zaten sıralıdır ve işlemden erken çıkarız. Bu, zaten sıralanmış girdiler için O(n) en iyi durum karmaşıklığı sağlar; kabarcık sıralamasının gerçek tek avantajı budur. Bu bayrak olmadan her zaman O(n²) karşılaştırma yapılır. Mülakatçılar, kabarcık sıralamasında iyileştirmeler sorulduğunda erken çıkış optimizasyonunu arar.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passKabarcık Sıralamasının Karmaşıklık Analizi
Kabarcık sıralamasının dış döngüsü n-1 kez çalışır. İç döngü, her geçişte n-1-i kez çalışır: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 karşılaştırma. Bu, ortalama ve en kötü durumda O(n²) karmaşıklık verir. Erken çıkış bayrağıyla sıralanmış girdiler için en iyi durum O(n) olur. Alan karmaşıklığı O(1)'dir; yalnızca yer değiştirme için geçici bir değişken gerekir. Kabarcık sıralaması kararlıdır: yalnızca kesin olarak büyük öğelerin yerini değiştirdiğimiz için eşit öğeler göreli sıralarını korur.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Eklemeli Sıralama: Sıralı Bir El Oluşturma
Eklemeli sıralama, iskambil kâğıtlarından oluşan bir eli sıralamayı taklit eder: sıradaki kartı (öğeyi) alın ve soldaki zaten sıralanmış kartlar arasındaki doğru konumuna yerleştirin. Değişmez, arr[0:i] aralığının her zaman sıralı olmasıdır. Her yeni öğe için yer açmak üzere daha büyük öğeleri sağa kaydırın. Bu yerinde çalışan, kararlı algoritma en kötü durumda O(n²), neredeyse sıralı verilerde ise en iyi durumda O(n) karmaşıklığındadır.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Eklemeli Sıralama Adım Adım
[3, 1, 4, 2] üzerinde eklemeli sıralamayı izleyin: i=1, anahtar=1, 3'ü sağa kaydırın → [1, 3, 4, 2]. i=2, anahtar=4, kaydırma yok → değişiklik yok. i=3, anahtar=2, önce 4'ü, sonra 3'ü sağa kaydırın → [1, 2, 3, 4]. Her öğe, doğru yuvasını bulana kadar solundaki öğelerle karşılaştırılır. İçteki while döngüsü, atamalar kullanarak kaydırmaları gerçekleştirir; bu, yer değiştirmeden daha hızlıdır, çünkü her kaydırma için bir atama gerekirken yer değiştirme için üç atama gerekir.
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Neredeyse Sıralı Verilerde Eklemeli Sıralama
Eklemeli sıralamanın en önemli özelliği O(n + terslikler) karmaşıklığıdır. Terslik, i < j olmasına karşın arr[i] > arr[j] olan (i,j) çiftidir. Yalnızca birkaç terslik içeren neredeyse sıralı dizilerde eklemeli sıralama son derece hızlıdır; basitliği ve önbellek dostu erişim düzeni sayesinde pratikte bazen birleştirmeli sıralamadan bile hızlıdır. Python'ın Timsort uygulaması, tam da bu nedenle küçük alt dizilerde eklemeli sıralama kullanır.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Sıralamada Kararlılık
Bir sıralama algoritması, eşit öğeler sıralamadan sonra özgün göreli sıralarını koruyorsa kararlıdır. Hem kabarcık sıralaması hem de eklemeli sıralama kararlıdır; eşit öğelerin yerini hiçbir zaman değiştirmezler. Birden çok anahtara göre art arda sıralama yaptığınızda kararlılık önemlidir: önce ikincil anahtara göre kararlı biçimde, ardından birincil anahtara göre yine kararlı biçimde sıralayarak eşit öğeler arasındaki ikincil anahtar sırasını koruyun. Birleştirmeli sıralama da kararlıdır; yığın sıralaması ve hızlı sıralama ise genellikle kararlı değildir.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableEklemeli Sıralamada İkili Arama
Eklemeli sıralamanın iç döngüsü hem doğru konumu bulur hem de öğeleri kaydırır. Konumu O(log i) karşılaştırmayla bulmak için ikili arama kullanabilirsiniz, ancak kaydırmalar yine O(i) zaman alır; bu nedenle toplam karmaşıklık O(n²) olarak kalır. Bu optimizasyon karşılaştırma sayısını azaltır (pahalı karşılaştırma işlevleri için yararlıdır), ancak toplam işlem sayısını azaltmaz. Bu "ikili eklemeli sıralama", küçük parça boyutları için Timsort'ta kullanılır.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Kabarcık ve Eklemeli Sıralama: Hangisi Ne Zaman Kullanılmalı
Mülakatlarda bu karşılaştırmayı kendinizden emin biçimde ifade edin: eklemeli sıralama, kabarcık sıralamasından kesinlikle daha iyidir; her ikisi de en kötü durumda O(n²) ve O(1) alan kullanır, ancak eklemeli sıralama daha az yazma işlemi yapar (k terslik için O(n+k), kabarcık sıralaması için O(n²)), önbellek kullanımına daha uygundur ve küçük n değerleri için pratik seçimdir (Timsort bunu kullanır). Kabarcık sıralamasının tek gerçek avantajı öğretici açıdan basit olmasıdır. Üretim ortamında her zaman dilin yerleşik sort işlevini kullanın.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Terslikleri Ölçüt Olarak Sayma
Bir dizideki tersliklerin sayısı, i < j olmasına karşın arr[i] > arr[j] olan (i,j) çiftlerinin sayısına eşittir. Eklemeli sıralama, tersliklerin sayısı kadar kaydırma yapar; bu yararlı bir gözlemdir. Terslikleri verimli biçimde saymak (O(n log n)) için değiştirilmiş birleştirmeli sıralama gerekir. Mülakatçılar, sıralama tartışmalarının devamında bazen "algoritmanız terslikleri ne ölçüde dikkate alıyor?" diye sorar.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedHızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: kabarcık sıralaması n-1 geçiş yapar ve her geçişte mevcut maksimumu nihai konumuna taşır; en kötü durumda O(n²), erken çıkış bayrağıyla en iyi durumda O(n) karmaşıklığındadır, eklemeli sıralama mevcut anahtarı doğru sıralı konuma yerleştirmek için öğeleri sağa kaydırır ve O(n + terslikler) zamanda çalıştığından neredeyse sıralı veriler için en uygunudur ve her iki algoritma da kararlı, O(1) alan kullanan ve en kötü durumda O(n²) karmaşıklığa sahip algoritmalardır; ancak tüm pratik senaryolarda eklemeli sıralama kabarcık sıralamasına kesinlikle tercih edilir. Sırada birleştirmeli sıralamayı sıfırdan uyguluyoruz.
Sıkça Sorulan Sorular
“Kabarcık Sıralaması ve Eklemeli Sıralama” dersi ücretsiz mi?
Evet — “Kabarcık Sıralaması 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 DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Kabarcık Sıralaması ve Eklemeli Sıralama” dersinde ne öğreneceğim?
Her iki karesel sıralama algoritmasını kodlayın, neden O(n²) olduklarını anlayın ve eklemeli sıralamanın birleştirmeli sıralamayı geçtiği tek durumu tanıyın. DSA Interview Prep 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.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, 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 Sıralaması 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 DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep 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 Sıralaması ve Eklemeli Sıralama
- Birleştirmeli Sıralama: Böl, Sırala, Birleştir
- Hızlı Sıralama ve Dönüm Noktası Seçimi
- Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi