Quick sort, merge sort ve heap sort'u karşılaştırın.
Cevap
| Quick sort | Merge sort | Heap sort | |
|---|---|---|---|
| Ortalama | O(n log n) | O(n log n) | O(n log n) |
| En kötü | O(n²) | O(n log n) | O(n log n) |
| Ek bellek | O(log n) yığın | O(n) | O(1) |
| Kararlı (stable) | Hayır | Evet | Hayır |
| Pratik hız | Genelde en hızlı (önbellek dostu) | İyi, bağlı listede ideal | Sabitleri yüksek |
- Quick sort: bir pivot seçer, küçükleri sola büyükleri sağa ayırır (partition), iki tarafı özyinelemeli sıralar. Kötü pivot seçimi (sıralı dizide hep ilk eleman)
O(n²)'ye yol açar; rastgele veya median-of-three pivot ile önlenir. - Merge sort: diziyi ikiye böler, her yarıyı sıralar, sıralı iki yarıyı birleştirir. Garantili
O(n log n)ve kararlıdır; harici sıralamada (diske sığmayan veri) kullanılır. - Heap sort: diziden max-heap kurar, kökü sona alıp heap'i küçültür. Yerinde ve garantili ama pratikte yavaştır.
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= kararlılığı korur
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]Kararlılık, eşit anahtarlı elemanların orijinal sırasını korumasıdır; örneğin önce isme sonra yaşa göre sıralarken önemlidir. Python'un sorted ve Java'nın nesne sıralaması Timsort (merge + insertion hibriti) kullanır.
İlgili Algoritmalar & Veri Yapıları soruları
- Binary search'ün zaman karmaşıklığı nedir ve neden?
- Two Sum: toplamı hedefe eşit olan iki elemanın indekslerini bulun.
- Bir parantez dizisinin geçerli olup olmadığını kontrol edin: "({[]})"
- Tek yönlü bağlı listeyi ters çevirin.
- BFS ve DFS arasındaki fark nedir? Hangisini ne zaman kullanırsınız?
- get ve put işlemleri O(1) olan bir LRU Cache tasarlayın.
Bu konuda başka bir soru biliyor musun?
Mülakatta karşılaştığın soruları ekle, onaylandıktan sonra yayına alınsın.