Merhaba,
Sıralama Algoritmaları yazı dizimizin ikinci bölümü ile karşınızdayım. Bu yazımızda sizlere selection sort yani seçmeli sıralama hakkında bilgiler aktarmaya çalışacağım.
Sıralama ve arama tekniklerinden pek çok programda yararlanılmaktadır. Günlük yaşamımızda elemanların sıralı tutulduğu listeler yaygın olarak kullanılmaktadır. Sıralama, sıralanacak elemanlar bellekte ise içsel kayıtların bazıları ikincil bellek ortamında ise dışsal sıralama olarak adlandırılır.
Seçmeli Sıralama Algoritması
•Dizideki en küçük elemanı bul, bu elemanı dizinin son(konum olarak) elemanıyla yer değiştir.
• Daha sonra ikinci en küçük elemanı bul ve bu elemanı dizinin ikinci elemanı ile yer değiştir. Bu işlemi dizinin tüm elemanları sıralanıncaya kadar sonraki elemanlar ile tekrar et.
•Elemanların seçilerek uygun yerlerine konulması ile gerçekleşen bir sıralamadır.
Örnek
9,5,8,3,1 rakamlarının azalan şekilde sıralanmasını seçmeli sıralama algoritması ile gerçekleştirelim.
Seçmeli Sıralama Kodu
public static int[] selectionSort(int[] A, int n) { int tmp, min; for(int i=0; i<n-1;i++) { min=i; for(int =i;j<n-1;j++) { if (A[j]<A[min]) { min=j; } } tmp=A[i]; A[i]=A[min]; A[min]=tmp; } return A; }
Performans
n elemanlı bir dizi için, seçerek sıralama algoritması yaklaşık n²/2 karşılaştırma ve n yer değiştirme işlemi gerçekleştirmektedir. Bu özelliği seçerek sıralama işlevinin gerçekleştiriminden çıkarmak mümkündür.
Dış döngünün her işletiminde bir tek yer değiştirme işlemi gerçekleştirildiğinden, bu döngü n adet işletildiğinde ( n = dizi boyutu ) n tane yer değiştirme işlemi gerçekleşecektir.
Bu döngünün her işletiminde ayrıca N-i adet karşılaştırma gerçekleştiğini göz önüne alırsak toplam karşılaştırma sayısı (n-1)+(n-2)+…+2+1 >>> n²/2 olacaktır.
Bu yazımızda da selection sort yani seçmeli sıralama hakkında bilgi verdik. Eğer anlamadığınız kısım veya eksik olduğunu düşündüğünüz yerler varsa bana yorumlar aracılığıyla iletebilirsiniz.
Teşekkürler!