Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi
Tamsayı dizileri için sayma sıralamasını ve basamak sıralamasını keşfedin; yerleşik sort çağrılarında Python’un Timsort algoritmasının arka planda nasıl çalıştığını anlayın.
Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. 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.
Karşılaştırmalar İçin O(n log n) Alt Sınırı
Sıralama düzenini yalnızca öğe karşılaştırmalarıyla belirleyen her sıralama algoritması, en kötü durumda en az Ω(n log n) karşılaştırma gerektirir. Bu, karar ağacı argümanıyla kanıtlanır: n öğeyi sıralamak, n! olası sıralamayı birbirinden ayırt etmeyi gerektirir. İkili bir karar ağacının (her düğüm bir karşılaştırmadır) en az log₂(n!) ≈ n log₂(n) düzeye sahip olması gerekir. Bu sınırı aşmak için öğeler hakkında, örneğin öğelerin sınırlandırılmış tamsayılar olması gibi, ek bilgilere ihtiyaç duyarız.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingSayma Sıralaması: Sıklığa Göre Sıralama
Sayma sıralaması, her değerin görülme sıklığını sayarak ve ardından sayımlardan sıralanmış diziyi yeniden oluşturarak çalışır. Değerlerin [0, k) aralığını önceden bilmek gerekir. Zaman karmaşıklığı: O(n + k); alan karmaşıklığı: O(k). n'e göre küçük k değerleri için (ör. 0-120 yaşları veya tek basamaklı sayıları sıralarken) sayma sıralaması tüm karşılaştırmalı sıralamaları geride bırakır. k büyük olduğunda O(k) alan maliyeti yöntemi pratik olmaktan çıkarır.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Kümülatif Sayımlarla Kararlı Sayma Sıralaması
Kararlı bir sayma sıralaması (nesneleri bir anahtara göre sıralarken önemlidir) için kümülatif sayımları hesaplayın; böylece cum[v], v değerinin çıktıda başlayacağı konumu verir. Girdi dizisini sağdan sola tarayın; her öğeyi cum[key] - 1 konumuna yerleştirin ve bu konumu bir azaltın. Böylece kararlı bir sıralama elde edilir; aynı anahtara sahip öğeler özgün göreli sıralarını korur.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Basamaklı Sıralama: Basamak Basamak Sıralama
Basamaklı sıralama, her basamak konumunda kararlı bir sıralama (sayma sıralaması gibi) kullanarak tam sayıları en düşük anlamlı basamaktan (LSD) en yüksek anlamlı basamağa (MSD) doğru basamak basamak sıralar. d geçişten (her basamak için bir geçiş) sonra dizi tamamen sıralanmış olur. Zaman karmaşıklığı: O(d × (n + k)); burada d = basamak sayısı ve k = taban (genellikle 10). W ile sınırlı n tam sayı için d = log_k(W) olduğundan toplam karmaşıklık O(n log_k(W)) olur.
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Kova Sıralaması: Kovalara Dağıtma
Kova sıralaması, öğeleri değer aralığına göre sabit sayıda kovaya dağıtır, her kovayı (küçük kovalar için eklemeli sıralama kullanarak) sıralar ve kovaları birleştirir. [0, 1) aralığında düzgün dağılımlı veriler için n kova, ortalama O(n) zaman sağlar. Zaman karmaşıklığı: ortalama O(n + k), en kötü durumda O(n²) (tüm öğeler tek kovadaysa). Veri dağılımının bilindiği ve yaklaşık olarak düzgün olduğu durumlarda en kullanışlıdır.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listPython'ın Timsort'u Nasıl Çalışır
Python'ın sorted() ve list.sort() işlevleri, Tim Peters tarafından 2002'de tasarlanan Timsort'u kullanır. Timsort, birleştirmeli sıralama ile eklemeli sıralamanın birleşimidir. “Doğal serileri” (zaten sıralanmış alt dizileri) tarar ve 64 öğeye kadar olan serileri oluşturmak için eklemeli sıralamayı kullanır. Ardından serileri, birkaç iyileştirmeyle birleştirmeli sıralamayı kullanarak birleştirir: hızlı atlama (bir seri baskın olduğunda öğeleri topluca atlama) ve seri uzunluklarını yığma.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Python'da sort() ve sorted(): Temel Farklar
list.sort() yerinde sıralama yapar, None döndürür ve yalnızca listeler üzerinde çalışır. sorted(iterable) her yinelenebilir üzerinde (demetler, üreteçler ve sözlükler gibi) çalışır ve yeni bir liste döndürür. Her ikisi de key ve reverse parametrelerini kabul eder. Yaygın bir hata, lst.sort() dönüş değerini bir değişkene atayıp neden None olduğunu merak etmektir. Sıralanmış sürüme ihtiyaç duyduğunuzda ve özgün listeyi korumak istediğinizde her zaman sorted() kullanın.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Mülakatlarda Özel Sıralama Anahtarları
Python'ın sıralama işlevi, her öğe için bir kez değerlendirilen bir key işlevini kabul eder (her çift için çağrılan C karşılaştırıcısının aksine). Mülakatlarda yaygın sıralama anahtarları şunlardır: dize uzunluğu için len, azalan sıralama için lambda x: -x, çok anahtarlı sıralama için lambda x: (x[1], x[0]) ve büyük-küçük harfe duyarsız sıralama için str.lower. Python'ın sıralaması kararlı olduğu garanti edildiğinden çok anahtarlı sıralamalar doğru çalışır.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Mülakatlarda Hangi Sıralama Ne Zaman Kullanılmalı
Bağlama uygun sıralamayı seçin:
- Python'ın sorted()/list.sort() işlevlerini kullanın: tüm mülakat soruları için varsayılan seçenektir; Timsort en uygun yöntemdir
- Sayma sıralaması: değerler küçük ve sınırları belirli tam sayılarsa (0'dan k'ye, k küçükken)
- Basamaklı sıralama: bit genişliği veya basamak sayısı bilinen çok sayıda tam sayıyı sıralarken
- Kova sıralaması: bilinen bir aralıkta düzgün dağılmış kayan noktalı verilerde
- Birleştirmeli sıralamayı uygulayın: sıfırdan kararlı bir O(n log n) sıralaması kodlamanız istendiğinde
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Sıralama Yapmadan Sıralama: Yığınla En İyi k Öğeyi Bulma
Birçok mülakat sorusu, tam bir sıralama gerektirmeden “sıralama benzeri” sonuçlar ister. En iyi k öğeyi bulmak için k boyutunda bir minimum yığını kullanmak O(n log k) sürer; k, n'den çok küçük olduğunda bu, O(n log n)'den daha hızlıdır. k'ıncı en büyük öğeyi bulmak için hızlı seçim ortalama O(n) sürer. Ortancayı bulmak için iki yığınlı yaklaşım, ekleme başına O(log n) sürer. Bu kısmi sıralama yaklaşımları, tam sıralamaya göre daha hızlı seçenekler olarak bilinmeye değerdir.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Çok Anahtarlı Sıralamada Sıralama Kararlılığı
Kararlılık, doğru çok anahtarlı sıralamayı mümkün kılar: önce ikincil anahtara göre kararlı biçimde sıralayın, ardından birincil anahtara göre yine kararlı biçimde sıralayın. Birincil anahtardaki eşitliklerde ikincil anahtarın sırası korunur. Bu teknik, veritabanlarında (ORDER BY col1, col2) ve basamaklı sıralamada kullanılır (genel algoritmanın doğru olması için her basamak geçişinin kararlı olması gerekir). Python'ın sıralaması her zaman kararlı olduğundan bu yöntem güvenilir biçimde çalışır.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: karşılaştırmaya dayalı sıralamaların alt sınırı O(n log n) ile belirlenir; bu sınırı aşmak için sınırları belirli tam sayılar gibi karşılaştırma dışı bilgiler gerekir, sayma sıralaması frekansları sayarak O(n + k) elde eder, basamaklı sıralama basamakları işler ve toplamda O(d × (n + k)) sürer, kova sıralaması ise düzgün dağılımdan yararlanarak ortalama O(n) sağlar ve Python'ın Timsort'u pratikte varsayılan seçenektir: kararlıdır, en kötü durumda O(n log n), en iyi durumda O(n) sürer ve gerçek verilerde elle yazılmış tüm seçeneklerden daha hızlıdır. Sırada klasik ikili aramayı öğreniyoruz.
Sıkça Sorulan Sorular
“Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi” dersi ücretsiz mi?
Evet — “Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi” 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.
“Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi” dersinde ne öğreneceğim?
Tamsayı dizileri için sayma sıralamasını ve basamak sıralamasını keşfedin; yerleşik sort çağrılarında Python’un Timsort algoritmasının arka planda nasıl çalıştığını anlayı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 4. dersidir.
“Karşılaştırmasız Sıralamalar ve Python’un sort() İşlevi” 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