Sıralama Algoritmaları: Hangisi Ne Zaman?
Bubble sort, insertion sort, merge sort ve quicksort yaklaşımlarını karmaşıklık, bellek ve kararlılık açısından karşılaştırın.
Siparişleri tarihe göre göstermek basit görünür. Ancak veri milyonlara çıktığında, neredeyse sıralı olduğunda veya belleğe sığmadığında doğru algoritma değişir.
Karşılaştırma ölçütleri
Time complexity işlem sayısının büyümesini, space complexity ek bellek ihtiyacını anlatır. Stable sort, eşit anahtarlı öğelerin ilk sırasını korur. In-place algoritma çok az ek bellekle çalışır.
Temel algoritmalar
Bubble sort komşu ters çiftleri tekrar tekrar değiştirir. Öğreticidir ama ortalama ve kötü durumda O(n²) olduğu için büyük veri için uygun değildir.
Insertion sort her öğeyi sıralanmış ön bölüme yerleştirir. Kötü durumda O(n²) olsa da küçük veya neredeyse sıralı listelerde iyi çalışabilir.
Merge sort diziyi ikiye böler, parçaları sıralar ve birleştirir. Zamanı güvenilir biçimde O(n log n) ve kararlıdır; tipik dizi uygulaması O(n) ek alan ister.
Quicksort bir pivot seçip küçük ve büyük değerleri ayırır. Ortalama O(n log n), kötü pivot seçiminde O(n²) olabilir. İyi uygulamalar rastgele pivot ve küçük parçalar için insertion sort gibi teknikleri birleştirir.
Comparator ne yapar?
orders.sort((a, b) => a.createdAt.getTime() - b.createdAt.getTime());Comparator negatif dönerse a önce, pozitif dönerse b önce, sıfırsa eşit kabul edilir. Boolean döndürmek comparator sözleşmesini bozar. Tarih metinlerini her karşılaştırmada parse etmek yerine önce normalize etmek daha verimli olabilir.
Alternatifler
Veri veritabanındaysa sıralamayı çoğunlukla ORDER BY ve uygun indeksle kaynağa yaptırmak gerekir. Yalnızca en büyük k öğe gerekiyorsa bütün listeyi sıralamak yerine heap ile O(n log k) çözüm kullanılabilir. Belleğe sığmayan veri için external merge sort tercih edilir.
Alıştırma
Ad ve yaş alanı olan kayıtları önce yaşa, yaş eşitse ada göre sıralayan comparator yazın. Stabilitenin sonucu hangi durumda etkilediğini örnekleyin.