Popüler sıralama algoritmalarının karşılaştırması
Sıralama algoritmaları geçmişten günümüze kullanılıp geliştirilmekte olup, programlamada önemli bir yer edinmiştir. Bu yazıda sıralama problemini çözmek için geliştirilmiş olan popüler 5 sıralama algoritmasının 100.000 adet rastgele sayı üzerinde zaman karmaşıklıklarını tablo ve grafiklerle incelemeye çalışacağız.
Karşılaştırılacak olan algoritmalar:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Quick Sort
- Merge Sort
Her bir algoritma için daha önceden bir text dosyasına yazılmış olan 100.000 adet rastgele sayıyı kullanacağız. Aynı sayı dizisi için algoritmaların çalışma süreleri aşağıdaki tablodaki gibidir:
Süre(s) | |
Bubble Sort | 28.855 |
Insertion Sort | 7.022 |
Selection Sort | 10.986 |
Quick Sort | 0.016 |
Merge Sort | 0.016 |
Tabloyu grafiklere döktüğümüzde ise aşağıdaki sonuçları elde edilmekte:
Görüldüğü üzere benzer bir yöntem ile sıralama gerçekleştiren Quick Sort ve Merge Sort aynı sürede sıralama yapmıştır. Diğer algoritmalar -özellikle Bubble Sort- ise bu iki algoritmaya göre bir hayli yavaş sıralama yapmaktadır. Bunun nedeni Quick Sort ve Merge Sort algoritmaları dışındaki algoritmaların O(n2) (n eleman sayısı) zaman karmaşıklığına sahip olmalarına karşın Quick Sort ve Merge Sort’un ağaç yapısında ayrıştırma yapması O notasyonun n2 ‘ye nispeten çok daha küçük olmasıdır: O(nlog2n).