Seçmeli Sıralama ( Selection Sort )

Neden Sıralıyoruz?
Elimizde bulunan her türlü bilgiye kolay ulaşmak için o bilgilerin belirli bir düzen ve sıra içinde olması, aradığımız bilgiye kolay ulaşmak için gerekli olan temel ihtiyaçlardan biridir. Basit örnek olarak; elimizde 100 tane gözü olan bir raf ve 1’den 100’e kadar numaralandırılmış 100 tane kitap olsun. Kitapların raflara belirli bir sıra ile değil de rastgele yerleştirilmiş olduğunu düşünürsek, 45 numaralı kitaba ulaşmak için en az 1, en fazla 100 rafa bakmamız gerekebilir. Ama kitapların raflara sırayla yerleştirirsek, istediğimiz numaralı kitaba tek bir rafa bakarak ulaşabiliriz. Elimizdeki bilgilerin sıralı olması bu gibi durumlarda, özellikle arama ( searching ) durumlarında işimizi oldukça kolaylaştıracaktır.
Birçok sıralama algoritması vardır. Bu algoritmalardan selection sort’a değinmeye çalışacağım:

Seçmeli Sıralama ( Selection Sort )
En basit sıralama algoritması olarak gösterilebilir. Elimizdeki dizide sıralanması gereken n tane sayı olsun. Bu sayıları küçükten büyüğe sıralamak gerekirse, sıralama algoritması şöyledir:
1- Dizinin 1. elemanından başlayarak tüm elemanlarını kontrol ederek en küçük sayıyı bul,
2- Bulduğun en küçük sayıyı dizinin 1. sayısıyla yer değiştir (swap).
3- Dizinin 2. elemanından başlayarak tüm elemanlarını kontrol ederek en küçük sayıyı bul,
4- Bulduğun en küçük sayıyı dizinin 2. sayısıyla yer değiştir (swap).
5- ……
6- Dizinin (n-1). elemanından başlayarak tüm elemanlarını kontrol ederek en küçük sayıyı bul,
7- Bulduğun en küçük sayıyı dizinin (n-1). sayısıyla yer değiştir (swap).
Her bir jenerasyonda en küçük sayıyı bulup onu swap ettiğimiz yer, o sayının sıralanmış dizideki uygun yeri olmuş oluyor.

Bir parça c kodu ile;

#include <stdio.h>
int main()
{
	int dizi[6] = { 10,1,9,2,8,3 };
	int n=6;
	int i,j,indexOfMin,temp;
	int min;

	for ( i=0;i<n-1;i++ )
	{
		min=dizi[i];
		indexOfMin=i;
		for ( j=i+1;j<n;j++ )
		{
			if( dizi[j]<min )
			{
				min=dizi[j];
				indexOfMin=j;
			}
		}
		temp=dizi[i];
		dizi[i]=min;
		dizi[indexOfMin]=temp;
	}
	printf("siralanmis dizi\n");
	for( i=0;i<n;i++ )
		printf("%d ",dizi[i] );
	printf("\n");
	return 0;
}

(21-23. satırlar arasında swap işlemi yapılıyor)
Kodda ufak değişiklikler yaparak büyükten küçüğe de sıralama yapmak mümkündür.

Karmaşıklık ( Complexity )
Sıralanmış dizinin herbir elemanını bulurken, sıralanmamış diziyi baştan sonra kontrol etmemiz gerekiyor.
1. en küçük elemanı bulurken n-1,
2. en küçük elemanı bulurken n-2,
3. en küçük elemanı bulurken n-3,
…..
(n-1). en küçük elemanı bulurken 1 tane kontrol yapılır. Yapılan tüm bu kontrollerin toplam sayısı:

( n X (n-1) ) / 2 tanedir. Seçmeli sıralamanın karmaşıklığı O(n2) olur.