İçeriğe geç
parazade
Yazılım & No-Code

Hızlı Sıralama Nedir?

İngilizce: Quick Sort

Yayın: · Son güncelleme:

Hızlı Sıralama Nedir? Kısaca

Hızlı sıralama (quick sort), listeden bir pivot eleman seçip diğer elemanları pivottan küçükler ve büyükler olarak ikiye ayıran, sonra her parçayı aynı yöntemle sıralayan böl ve yönet algoritmasıdır.

Hızlı Sıralama nedir?
İçindekiler
  1. Hızlı sıralama nedir?
  2. Nasıl çalışır?
  3. Performansı

Hızlı sıralama nedir?

Hızlı sıralama, Tony Hoare'un 1959'da geliştirip 1961'de yayımladığı ve bugün de en çok kullanılan sıralama algoritmalarından biridir. Böl ve yönet yaklaşımıyla çalışır. Büyük bir sıralama problemini, sıralanması daha kolay küçük parçalara böler.

Nasıl çalışır?

Algoritma üç adımda ilerler. Önce listeden pivot adı verilen bir eleman seçilir. Ardından diğer elemanlar pivottan küçükse sola, büyükse sağa yerleştirilir. Son olarak sol ve sağ parçalar, aynı yöntemle özyineleme kullanılarak sıralanır. Tek elemanlı parçalar zaten sıralı sayıldığı için bölme orada durur.

Örnek olarak 7, 2, 9, 4, 5 listesini alalım ve pivot olarak son eleman olan 5'i seçelim. Küçükler 2 ve 4, büyükler 7 ve 9 olur. Liste şimdi [2, 4], 5, [7, 9] düzenindedir. İki küçük parça da kendi içinde sıralanınca sonuç 2, 4, 5, 7, 9 olur.

Performansı

Ortalama durumda hızlı sıralama O(n log n) sürede çalışır ve ek belleğe pek ihtiyaç duymadan yerinde sıralama yapar. Bu yüzden pratikte çoğu algoritmadan hızlıdır.

Zayıf noktası pivot seçimidir. Pivot her seferinde en küçük ya da en büyük eleman olursa, örneğin zaten sıralı bir listede hep son elemanı seçerseniz, bölmeler dengesizleşir. Bu durumda süre O(n²) seviyesine çıkar. Rastgele pivot seçimi ya da ilk, orta ve son elemanın ortancasını almak bu riski büyük ölçüde azaltır. Pek çok dilin hazır sıralama fonksiyonu da hızlı sıralamanın bu iyileştirilmiş türevlerini kullanır.

Sıkça Sorulan Sorular

Pivot nasıl seçilir?

İlk, son, ortadaki ya da rastgele bir eleman seçilebilir. Pratikte rastgele seçim veya üç elemanın ortancasını almak, en kötü durumla karşılaşma ihtimalini azaltır.

Hızlı sıralama kararlı mıdır?

Klasik hâliyle kararlı değildir. Eşit değerli elemanların göreli sırası değişebilir; sıranın korunması gerekiyorsa birleştirmeli sıralama tercih edilir.

İlgili terimler

Sıralama Algoritmaları(Sorting Algorithms)Sıralama algoritmaları, bir listedeki elemanları küçükten büyüğe, alfabetik ya da başka bir ölçüte göre dizmek için kullanılan adım adım yöntemlerdir. Hız, bellek kullanımı ve kararlılık bakımından birbirinden ayrılırlar.Birleştirmeli Sıralama(Merge Sort)Birleştirmeli sıralama (merge sort), listeyi tek elemanlı parçalara kadar ikiye bölen, sonra bu parçaları sıralı biçimde birleştirerek bütün listeyi sıralayan böl ve yönet algoritmasıdır. Her durumda O(n log n) sürede çalışır.Özyineleme(Recursion)Özyineleme (recursion), bir fonksiyonun bir problemi çözmek için kendini daha küçük bir girdiyle yeniden çağırmasıdır. Her özyinelemeli fonksiyonda çağrıları durduran bir temel durum bulunmalıdır, yoksa program sonsuza kadar kendini çağırır.Big O Notasyonu(Big O Notation)Big O notasyonu, bir algoritmanın çalışma süresinin ya da bellek kullanımının girdi büyüdükçe nasıl arttığını ifade eden matematiksel gösterimdir. Algoritmaları donanımdan bağımsız biçimde karşılaştırmayı sağlar.Algoritma(Algorithm)Algoritma, belirli bir problemi çözmek ya da bir görevi yerine getirmek için izlenen, sırası ve sonu belli, açık ve uygulanabilir adımlar dizisidir. Bilgisayar programları ve yapay zekâ sistemleri algoritmalar üzerine kuruludur.Liste(List)Liste (list), programlamada birden fazla değeri sıralı tutan, eleman eklenip çıkarılabilen ve değiştirilebilen veri yapısıdır. Python'da köşeli parantezle yazılır: `meyveler = ["elma", "armut"]`.LogLog, bir yazılımın ya da sistemin çalışırken gerçekleşen olayları tarih ve saatiyle kaydettiği kayıttır. Hataları bulmak, kullanıcı hareketlerini izlemek ve güvenlik olaylarını incelemek için kullanılır.