Sıralama algoritmalarına değindiğimiz makale serimizin bu bölümünde Selection Sort yani Seçmeli Sıralama algoritmasından bahsedeceğiz. Bu algoritmada her bir iterasyonda en küçük eleman tespit edildiği için seçerek sıralama algoritması adını almıştır.
İterasyon bittiğinde yani dizinin son elemanına gelindiğinde değerler içerisinden tespit edilen en küçük değer başa alınarak birinci eleman yapılır. Sonraki iterasyonlarda ise küçük sayısı arama işlemine bir sonraki sayıdan (ikinci sayıdan, üçüncü sayıdan, dördüncü sayıdan,….n.sayıdan) başlanılarak küçükten büyüğe olacak şekilde sola kaydırılır. Yani önceki iterasyonda sıralanan işi biten eleman sonraki iterasyonlara dahil edilmez.
Hatırlatma:
Insertion Sort algoritmasında ikili ikili bakılıyor ve büyük mü küçük mü sorusu iki değer arasında yapılıp diğer elemanlara geçiliyordu. Yani sıralamayı tamamlamak için son elemana kadar gitmesine gerek kalmıyordu. Her bir iki elemana bakıp sıraladıktan sonra diğer iki elemana geçiyordu. Ancak sıralamada yer değişim için araya sokabiliyordu. 5. eleman 2. elemandan küçükse 5. elemanı 2’nin yanına sokabiliyordu.
Bubble Sort algoritmasında ise intertion sort algoritması gibiydi ancak tek kötü yanı tespit edilen küçük değer olması gerektiği sıraya o an sokulamıyordu. Kendi arasında sıralanıyor iterasyon bitiyor diğer iterasyonda tekrar bakılıyordu. Yani yine elemanlara ikili ikili bakılıyordu diyebiliriz. 5. eleman 4. elemandan küçükse kendi aralarında yer değiştiriyorlar ancak 5. eleman 2. elemandan da küçükse 5. eleman 2. eleman ile yer değiştiremiyor araya giremiyordu.
Selection Sort algoritmasında dizi içerisinde gezilip en küçük eleman bulunup 1. eleman olarak işaretlenir. Daha sonra diğerlerine bakılıp en küçük tespit edilip 2. eleman olarak işaretlenir ve bu şekilde algoritma kendisini sonlandırana kadar devam eder.
Zaman Karmaşıklığı:
İç içe iki tane loop olduğundan en iyi ve en kötü durumda yani Worst ve Best Case’de O(N^2) dir. Dizi küçükten büyüğe sıralı bile gelse tüm elemanları gezeceği için bu durum böyle olmaktadır.
Örnek:
20,15,5,1,9,13 sayı dizisini selection sort algoritması ile sıralayalım.
- Dizinin ilk elemanını minimum değer olarak alıp bu değerin dizinin tüm elemanları ile kıyaslanmasını sağlayalım.
- 20 diğer elemanlar ile kıyaslanır ve hemen yanındaki 15 daha küçük olduğundan artık yeni mininum değer 15 olur.
- 15 dizideki tüm eleman ile kıyaslanır 5 daha küçük olduğu görülür ve yeni minimum değer 5 olarak devam edilir.
- bu şekilde tüm elemanlar kontrol edilir ve her bir iterasyonda küçük değer tespiti yapılıp sıralama yapılır. Sonra ikinci iterasyona geçilir ve aynı işlemler tekrar edilir.
- sonuçta sıralanmış dizi elde edilir.
Bu konuyla ilgili sorularınızı alt kısımda bulunan yorumlar alanını kullanarak sorabilirsiniz.
Referanslar
Algoritmalara Giriş: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
TAGs: Selection Sort, Sorting Algorithms,Sıralama algoritması nedir, Selection Sort nedir, Seçmeli Sıralama nedir
