Iyilestirilmis Selection Sort

Merhaba arkadaşlar bugün konumuz sıralama algoritmalarından Selection Sort...

Sıralama algoritmaları bize bilgisayar ortamında az maliyet ve kısa zamanda sıralama yapmamız için büyük olanaklar sağlıyor. Bir algoritmayı daha hızlı hale getirmek yada daha hızlısını bulmak hem dünya hemde bizim için büyük bir adım olacaktır. Ama bunları yaparken bellekten de  kayıp vermemeye çalışmalısınız. Ben selection sort üzerinde bir tür değişikliğe gittim. Daha hızlı olsun istedim ama bellekten de biraz fazla yer kullandığımı söyleyebiliriz. Daha fazla değişkene ihtiyacım oldu çünkü tüm sistemlerde bir ödünleşim sistemi olduğunu biliyoruz eğer bir yerden artırmaya çalışırsanız bir yerden kısmanız gerekir. Benim durumumda bu oldu. Daha hızlı ama daha çok bellek kullanan bir algoritma...

Yukarıdaki resimde göreceğiniz üzere on altı bin elemanı asıl selection sort 578 milisaniyede sıralarken değişikliğe uğrayan algoritma 486 milisaniyeye kadar düştü bilgisayarın durumuna göre bunlar değişiklik gösterebilir de...

Peki selection sort nedir ve nasıl bir değişikliğe gidilebilirdi?

Selection sort sıralama algoritması dizide ki en küçük elemanı bulup en başa koyup kalan elemanlar arasında sıralama bitene kadar yani elinizdeki sayıların tamamını kontrol edene kadar tekrarlıyordu.
Eğer 100 eleman varsa her birine bakıyordu. Peki ben tüm elemanlar içinden en küçüğü arıyorsam neden en büyüğü de aramayayım?
2 5 89 7 1 4
gibi bir dizinin orjinal selection sort kullanılarak sıralaması şu şekilde olacaktır
1)bulunduğun elemanı en küçük olarak belirle
2)sonra diziyi kontrol et en küçüğü bul
3)varsa sayıların yerini değiştir
2 5 89 7 1 4
kırmızı sayımız en küçük seçilmişti sonra dizi arandı ve 1 bulundu. değişimi uygulayalım
1 5 89 7 2 4
artık ilk elemanımız en küçük kalan elemanlarıda bu şekilde devamına ekleyebilir aramaya ikinci eleman olan 5 ten başlamalıyız.
5 en küçük seçilir ve dizinin en küçüğü bulunur.
1| 5 89 7 2 4
bu iki sayı tekrar yer değiştirilir.
1 2 89 7 5 4
bu şekilde tüm elemanları 6 defada sıralayabilirsiniz.

Ne demiştik tüm elemanlar içinden en küçüğü alıp en başa koyarken neden en büyüğü de bulmayayım.Peki bu bana ne kazandıracak?
Verdiğimiz örneği bu mantıkla incelersek

2 5 89 7 1 4
algoritma şu şekilde gidecek:
1) bulunduğun elemanı hem en büyük hem en küçük olarak belirle
2)tüm dizi içinde en büyüğü ve en küçüğü bul
3)en baştaki eleman ile en küçüğü sondaki eleman ile en büyüğü yer değiştir

2 5 89 7 1 4

Kırmızı sayımız şuanda bulunduğumuz eleman en küçük ve en büyük seçilen elemanımız.
mor sayı dizinin en büyük elemanı turuncu sayı en küçük eleman.Algoritmayı uygulayalım
1| 5 4 7 2 |89
şimdi 5 i seçip aynı algoritmayı sıralanmamış sayılara uygulayın ve tüm elemanlar 3 defada sıralanmış olacaktır.
Hemen işlemi yarısına düşürmüş olduk. yani 16000 sayı varsa Asıl selection sort 16000 defada sıralarken biz bunu 8000 defada sıralayabiliyoruz...

kodlama dili çok da önemli değil. Kullandığımız yapılar her dilde olduğundan sorun olmayacaktır...

Kod C#