Sıralama Algoritması
- İngilizcesi
- Sorting Algorithm
- Okunuşu
- sorting elgıridım
Kısaca
Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
Sıralama algoritması nedir?
Sıralama algoritması, bir listenin öğelerini sayısal, alfabetik ya da tarihe göre gibi bir kurala göre sıraya koyar. Sıralama önemlidir, çünkü ikili arama, yinelenenleri kaldırma, listeleri birleştirme ve medyanı bulma dahil birçok başka iş sıralı veride çok daha hızlı hale gelir. Algoritmalar zaman karmaşıklıklarına, ihtiyaç duydukları ek belleğe ve kararlı (stable) olup olmadıklarına göre karşılaştırılır.
Bubble sort, selection sort ve insertion sort gibi basit algoritmalar ortalamada O(n^2) sürer; bu büyük listelerde yavaşlar, ancak insertion sort küçük ya da neredeyse sıralı girdide hâlâ hızlıdır. Merge sort listeyi ikiye böler, her yarıyı sıralar ve sonuçları O(n) ek bellek kullanarak O(n log n) sürede birleştirir. Quicksort bir pivot seçer ve öğeleri onun etrafında bölümler; ortalamada O(n log n) sürer ama en kötü durumda O(n^2)'ye düşer. Heap sort ise O(1) ek bellekle O(n log n) garanti eder. Yalnızca öğeleri karşılaştırarak sıralayan herhangi bir algoritma en kötü durumda n log n mertebesinde karşılaştırma gerektirir; ancak counting sort ve radix sort öğeleri doğrudan karşılaştırmadıkları için tamsayılar ya da kısa anahtarlar için bunu aşabilir.
Bir el dolusu oyun kartını sıralamak iyi bir benzetmedir: çoğu kişi kartları tek tek alır ve elindeki kartlar arasında doğru yere kaydırır; insertion sort tam olarak böyle çalışır. Gerçek kodda kendi sıralamanızı nadiren yazarsınız. Python'ın sorted() ve list.sort() fonksiyonları merge sort ile insertion sort'un bir melezi olan Timsort'u kullanır, modern JavaScript motorları da Array.prototype.sort() için benzer kararlı O(n log n) algoritmaları kullanır.
Kararlılık sık bir karışıklık kaynağıdır. Kararlı bir sıralama, eşit anahtarlı öğelerin özgün göreli sırasını korur; yani siparişleri önce tarihe göre, sonra kararlı biçimde müşteriye göre sıralarsanız her müşterinin siparişleri tarih sırasında kalır. Python'ın sıralaması kararlıdır ve JavaScript'inkinin ES2019'dan beri kararlı olması zorunludur. JavaScript'te sort() fonksiyonunu karşılaştırma fonksiyonu olmadan çağırmak öğeleri string'e dönüştürür; bu yüzden [10, 9, 1].sort() ifadesi [1, 10, 9] döndürür; sayıları değerlerine göre sıralamak için (a, b) => a - b verin.
Önemli noktalar
- Bubble, selection ve insertion sort gibi basit sıralamalar O(n^2) sürede çalışır.
- Merge sort ve heap sort en kötü durumda bile O(n log n) sürer; quicksort ortalamada O(n log n) olur ama O(n^2)'ye çıkabilir.
- Yalnızca karşılaştırmayla sıralama, en kötü durumda O(n log n)'i aşamaz.
- Kararlı bir sıralama eşit öğeleri özgün sırasında tutar.
- Dilinizin hızlı ve iyi test edilmiş yerleşik sıralamasını tercih edin.
Örnek
def insertion_sort(items):
# O(n^2) in the worst case, but close to O(n) on nearly sorted input
for i in range(1, len(items)):
current = items[i]
j = i - 1
# Shift larger items one step right to make room for current
while j >= 0 and items[j] > current:
items[j + 1] = items[j]
j -= 1
items[j + 1] = current
return items
print(insertion_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
print(sorted([5, 2, 9, 1, 5, 6])) # built-in, O(n log n): same resultSık sorulan sorular
En hızlı sıralama algoritması hangisidir?
Her girdi için en hızlı olan tek bir algoritma yoktur. Genel amaçlı sıralamada, birkaç daha basit algoritmayı birleştiren Timsort ve introsort gibi O(n log n) melezleri pratik seçimdir; counting sort ve radix sort ise sınırlı aralıktaki tamsayılar için daha hızlı olabilir.
JavaScript sayıları neden yanlış sıralıyor?
Varsayılan olarak Array.prototype.sort() öğeleri string'e dönüştürür ve karakter karakter karşılaştırır; bu yüzden 10, 9'dan önce gelir. Sayıları değerlerine göre sıralamak için (a, b) => a - b gibi bir karşılaştırma fonksiyonu verin.
Bir sıralama algoritmasının kararlı olması ne demektir?
Kararlı bir algoritma, eşit karşılaştırılan öğeleri sıralamadan önceki göreli sırasında tutar. Bu, kayıtları önce bir alana sonra başka bir alana göre sıraladığınızda önemlidir; çünkü ilk sıralama ikincinin her grubu içinde korunur.
İlgili sayfalar
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- İkili AramaVeri Yapıları, s. 21İkili arama, sıralı bir listedeki bir değeri arama aralığını sürekli yarıya bölerek bulan bir algoritmadır; her öğeyi denetlemek yerine O(log n) sürer.
- HeapVeri Yapıları, s. 19Heap, en küçük ya da en büyük öğeyi kökünde tutan ağaç tabanlı bir veri yapısıdır; bu öğeyi O(1)'de okuyabilir ve O(log n)'de çıkarabilirsiniz.
- ÖzyinelemeProgramlamanın Temelleri, s. 42Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- Bubble SortVeri Yapıları, s. 7Bubble sort (kabarcık sıralaması), sırası bozuk komşu öğeleri yer değiştiren basit bir sıralama algoritmasıdır; her geçiş kalan en büyük değeri sona taşır.
- Insertion SortVeri Yapıları, s. 20Insertion sort (eklemeli sıralama), sıralı listeyi öğe öğe kurar; her yeni öğeyi sıralanmışlar arasında yerine koyar, tıpkı eldeki kartları dizmek gibi.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin