Seçerek Sıralama (Selection Sort)

Seçerek Sıralama (Selection Sort)

Yazan : Şadi Evren ŞEKER

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.

Yorumlar

  1. Reply
    Okan

    Sayın Şadi Evren ŞEKER, size ne kadar teşekkür etsem azdır.Selection Sort ile ilgili bir çok kaynak araştırdım nette ama bu kadar ince ve ayrıntılı anlatan bir kaynak bulamadım.Hhep içimde bir ukte kalmıştı bu algoritma nasıl çalışıyor, nasıl ilerliyor diye.Şimdi çok daha iyi anladım tekrar teşekkür ederim size.Sağolun!

  7. Reply
    frauzer

    Hocam elinize sağlık yalnız son elemanı kontrol etmiyor galiba. Bu şekilde yaptım düzeldi birde siz göz atın.
    for(int j=i; j <= n-1; j++)
    {
    if (A[j] < A[min]){

    min=j;
    }

    }

  8. Reply
    Şadi Evren ŞEKER Article Author

    Evet sanırım haklısınız. Öncelikle kodun orjinal halini bir sınıf içerisinde kodladım:

    public class siralama{
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-1; j++)
      {
        if (A[j] < A[min]){

          min=j;
        }

      }
        tmp=A[i];
        A[i]=A[min];
        A[min]=tmp;
    }
    return A;
  }
    public static void main(String args[]){
        int a[] = {6,4,2,3,1,5};
        a = selectionsort(a,6);
        for(int i = 0;i<6;i++)
            System.out.println(a[i]);
    }
}

    Ekran çıktısı aşağıdaki şekilde:

    ses3:ecm sadievrenseker$ java siralama
1
2
3
4
6
5
ses3:ecm sadievrenseker$

    Şimdi sizin uyarınızı dikkate alarak koddaki 11. satırda bulunan n-1 değerini kaldırıyoruz:

    public class siralama{
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-1; j++)
      {
        if (A[j] < A[min]){

          min=j;
        }

      }
        tmp=A[i];
        A[i]=A[min];
        A[min]=tmp;
    }
    return A;
  }
    public static void main(String args[]){
        int a[] = {6,4,2,3,1,5};
        a = selectionsort(a,6);
        for(int i = 0;i<6;i++)
            System.out.println(a[i]);
    }
}

    ve kodun çıktısı aşağıdaki gibi oluyor:

    ses3:ecm sadievrenseker$ javac siralama.java
ses3:ecm sadievrenseker$ java siralama
1
2
3
4
5
6
ses3:ecm sadievrenseker$

    İlginiz ve uyarınız için çok teşekkürler, yazıda da düzeltiyorum.

  9. Reply
    selim

    Hocam ellerinize sağlık gerçekten çok yalın anlatmışsınız fakat size algortima hakkında bir sorum olacak :
    Hocam bu algoritmanın diğer algoritmalara göre avantajları ve dezavantajları nelerdir?
    Bu algoritmayı başka nerelerde kullanabiliriz ?

  10. Reply
    neslihan

    çok teşekkür ederim size.Konuyu anladım fakat biz algoritmaları yazarken daha sayısal bir biçimde yazıyoruz.Bu şekilde hiçbir yerde örnek bulamıyorum.O yüzden bu sözel şeyleri sayısala geçiremiyorum bu konuda biraz yardımcı olsanız..
    mesela i’yi bir arttır diye bir şey kullanmıyoruz. i =i + 1 diyerek i’ye değer atıyoruz.O yüzden internetten pek faydalanamıyorum açıkcası.

  11. Reply
    Sena

    hocam selection sort rastgele diziye atanmış 10 sayıyı küçükten büyüğe sıralanmış c++ nın akış diyagramını da yapar mısınız

  12. Reply
    mahmut

    n-1 değerini kaldırıyoruz demişssiniz ama kaldırmamışsınız kafam çok karıştı ben mi fark göremiyorum yoksa ilk yorumla ikinci yorum arasında lütfen biri açıklasın

  13. Reply
    I NEED YOUR HELP

    int main(){

    int i,gec,a;
    printf(“dizi kac elemanli olsun”); scanf(“%d”,&a);
    int dizi[a];
    for(i=0;i<a;i++){

    printf("%d. sayiyi gir",i+1); scanf("%d",&dizi[i]);
    }

    for(i=0;i<a;i++){

    for(int j=0;j<a;j++){

    if(dizi[j]<dizi[i]){

    gec=dizi[i];
    dizi[i]=dizi[j];
    dizi[j]=gec;
    }
    }

    }
    for(i=0;i<a;i++){
    printf("\n%d",dizi[i]);

    }

    getch ();
    return 0;

    }

    HOCAM ÖNCELİKLE TÜRKCE KAYNAK OLUSTURMAK ACISINDAKİ VİZYONUNUZ İÇİN SİZİ HEP TAKTİR ETMİSİMDİR ALLAH RAZI OLSUN DEMEK İSTERİM SORUMA GELİNCE YUKARIDAKİ YAZDIGIM KODDA ELİME KALEM ALIP KODDAKİ ADIMLARI TEK TEK DÜŞÜNÜYORUM VE EN SONUNDA KÜÇÜKTEN BÜYÜĞE DOGRU SIRALAMASI GEREKTİĞİ KANAATİNE VARIYORUM AMA SONUC BÜYÜKTEN KÜÇÜĞE SIRALIYOR İF İÇİNDEKİ YAPINCA DÜZELİYOR AMA GERCEKTEN MANTIĞINI ANLAMADIM Bİ SEKİLDE YARDIMCI OLURSANIZ COK SEVİNİRİM TEKRARDAN TESEKKÜRLER…

  14. Reply
    eda

    c++ da bu şekilde yapılabilir
    #include
    using namespace std;
    const int elemansayisi=6;
    void selectionSort(int A [] ,int n){
    int tmp;
    for(int i=n-1; i >0; i–) {
    for(int j=0; j A[i]){
    tmp=A[i];
    A[i]=A[j];
    A[j]=tmp;
    }
    }
    }
    for(int i=0;i<n;i++)
    { cout<<A[i]<<" ";
    }
    }
    int main() {
    int A[] = {6,4,2,3,1,5};
    cout<<endl;
    selectionSort(A,elemansayisi);
    }

  15. Reply
    Yasin

    ”
    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
    ”
    İterasyonlar tek tek yazılırken şu aşamada bir yanlışlık söz konusu. En üstteki 1,2,3,5,9,6,7,7 iterasyonu 1,2,3,5,6,9,7,7 şeklinde ilerlemeli. 6 sayısı ile 9 sayısının yeri değiştirilmeli.

    Doğru iterasyonlar yanlış yerden itibaren aşağıdaki gibidir.

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

  16. Reply
    HASAN

    Hocam iyi günler.Bize derste daha ayrıntıya girilip serilerle zaman hesabının ispatı isteniyorda.Bir sorum olacaktı. Döngülerde,değişken tanımlamalarda T(n) deki n leri neye göre belirliyoruz tam olarak anlayamadım. Cevabını da bir türlü bulamıyorum da .

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir