Seçerek Sıralama (Selection Sort) - Java Örneği

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe her adımda dizideki en küçük sayının nerede olduğu bulunur. Bu sayı ile dizinin başındaki sayı yer değiştirilerek en küçük sayılar seçilerek başa atılmış olur.

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3,7

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Seçerek sıralamanın çalışması yukarıdaki bu örnek dizi üzerinde adım adım gösterilmiştir.

0. adım: başlangıç adımı i=0 olarak ata.

1. adım: dizideki i. sırasından sonraki en küçük sayının yerini bul. Bu dizideki en küçük sayı 1’dir ve 5. sıradadır.

2. adım dizinin i. sırasındaki sayıyı bu en küçük sayı ile yer değiştir: 1,7,2,9,6,5,3,7

3. adım : i’yi bir arttır ve 1. adıma git.

Dolayısıyla 3. adımdan sonra i=1 olacak ve sonra ilk sayı olan 1 atlanaraka kalan sayılar olan 7,2,9,6,5,3,7 sayıları arasından en küçük sayı bulunur. Bu sayı 2’dir ve sırası da 2dir. sıradaki sayı olan yerdeki sayı ile yer değiştirir ve sonuç : 1,2,7,9,6,5,3,7 olarak bulunur.

Artık i değeri 2dir ve bu sayıdan itibaren en küçük sayı 7,9,6,5,3,7 arasında aranır. bulunan 3’ün sırası 6’dır. Bu sayı da sıradaki yerini alır ve sonuç : 1,2,3,9,6,5,7,7 olur. Bu işlem böylece devam eder ve dizinin değişimi aşağıda gösterilmiştir:

1,2,3,5,9,6,7,7

1,2,3,5,6,9,7,7

1,2,3,5,6,7,9,7

1,2,3,5,6,7,7,9

olarak bulunur.

Bu işlemi yapan örnek bir JAVA kodu aşağıda verilmiştir:

public static int [] selectionsort(int [] A,int n)
  {
    int tmp;
    int min;

    for(int i=0; i < n-1; i++)
    {
      min=i;

      for(int j=i; j < n; j++)
      {
        if (A[j] < A[min]){

          min=j;
        }

      }
        tmp=A[i];
        A[i]=A[min];
        A[min]=tmp;
    }
    return A;
  }

Yukarıdaki örnek kodda iki döngü iç içe yazılarak içteki döngüde en küçük sayı bulunmuş, dıştaki döngüde ise bu işlemin her seferinde yenilenmesi sağlanmıştır.

Bu algoritmanın karmaşıklığı O(n2) ‘dir çünkü her adımda n sayı işlenmekte ve bu işlem n kere tekrar edilmektedir.