 |
| Seçerek Sıralama |
Bilgisayar mühendisliği okuyan kişilerin en çok sorduğu sorulardan biri de selection sort nedir sorusudur. Selection sort mantık olarak dizideki en küçük elemanı bulur ve en baştaki ile değiştirir. Yani swap işlemi yapar.( Swap nedir diye soruyorsanız linke tıklayarak ilgili yazıya ulaşabilirsiniz. )
Peki bu sistem nasıl dönüyor derseniz, her adımda baştaki indis değiştirilir. Böylece sıralanmış olur. Mantık olarak dizinin tüm elemanlarını tarayıp en küçük elemanı başa getirdiğimizde dizimizin sıfırıncı indisine doğru sayıyı koymuş oluyoruz. Aynı işlemi diğer adımda 1. indis için yapıyoruz. Böylece tüm indislere en küçük sayıları yerleştiriyoruz.
Selection Sort Algoritması Temel Mantığı
1. adım: Minimum indis tayin edilir. Başlangıç için bu değer sıfırdır.
2. adım: minimum indis de dahil olmak üzere tüm dizi taranır en küçük sayı bulunur.
3. adım: Eğer minimum indisten küçük değer bulunursa swap işlemi gerçekleşir.
Hoop:!!! bir saniye nasıl ya? sıkıntı var. Nedir sıkıntı? birden fazla küçük sayı varsa hangisini atayacağız? Cevap: Tabii ki en küçüğünü. Soru: peki o zaman en küçüğünü nasıl bulacağız? Hah, bu soru işin ayrıntı kısmı, tabii ki ayrıntılar halledilmezse algoritma çözülmez.
Bir dizideki en küçük eleman nasıl bulunur?
çok basit! minimum diye değer oluştururuz.
int minimum=dizi[0];
ne yaptık? başlangıç değeri olarak dizimizin 0. indisini minimum değerine atadık. Mevzu şu, minimum değerine en küçüğü atayacaksak, minimum değişkeninin mantıklı bir değeri olması lazım. Mesela 0 verirsek hiçbir işe yaramaz ya da yaramayabilir. Şimdi diziyi tarıyorum;
for(int i=0; i<n; i++)
{
if(dizi[i]<minimum)
minimum = dizi[i];
}
işte bu kadar. Dizinin tüm elemanları taranır, eğer minimuma atanmış değerden daha küçüğü bulunursa o küçük değer minimuma atanır. Mevzu budur.
Şimdi Selection Sort Algoritmasına geri dönelim.
Minimum indisi tayin et
Minimum indisten sonra (kendisi de dahil aman ha!) dizideki tüm elemanları tara
En küçük sayıyı tayin et.
(eğer varsa) minimum indisteki sayıyla swap et
minimum indisi bir artır.
Hah, bu algoritma daha net oldu bakın.
Peki bunu gerçek sayılar üzerinde uygulayalım
Adım Adım Selection Sort Algoritması İşleyişi
Elimizdeki sayılar; 3 9 7 2 1 8
1. iteration: 0 sayısını minimum değeriniz. bu mantıkla dizi[mininmum] yaklaşımıyla tara yapılır.
(mor renkli olan sayı minimum değeridir, mavi olan olan ise dizideki en küçük elemandır)
3 9 7 2 1 8
1. Sıralama İşlemi
1 sayısı dizideki en küçük elemandır ve 3'ten küçüktür. Swap işlemi gerçekleşir. (kırmızı renkli olan sayı sıralanmıştır, işi bitmiştir. Bundan sonra değerlendirmeye alınmaz.)
1 9 7 2 3 8
2. iteration: minimum değeri her adımda 1 artırılacağından artık minimum değeri 1 olur. dizi[1] değerinden itibaren karşılaştırma yapılır. (yani bu değer 9'dur)
1 9 7 2 3 8
2. Sıralama İşlemi
2 sayısı dizi[1] değerinden sonraki sayılar içerisinde en küçük elemandır ve dizi[1] değerinden daha küçüktür. Bu yüzden swap gerçekleşir.
1 2 7 9 3 8
3. iteration: Minimum değeri bir artar ve 2 olur. dizi[minimum] ifadesi de 7 değerine karşılık gelir.
1 2 7 9 3 8
3 sayısı 7 değerinden sonraki sayılar içerisinde en küçük sayıdır. 7 değerinden de küçüktür. Dolayısıyla yer değiştirme işlemi yapılır. böylece 3 sayısı da sıralı olarak işaretlenir.
1 2 3 9 7 8
3. Sıralama İşlemi
4. Adım: Minimum değeri 1 artar ve 3 olur. dizi[minimum] ifadesi 9 değerine tekabül eder.
1 2 3 9 7 8
4. Sıralama İşlemi
7 sayısı en küçük sayıdır, 9'dan da küçüktür. Dolayısıyla yine bir swap işlemi yapılır.
1 2 3 7 9 8
5. Adım: Minimum değeri yine 1 artırılır ve 4 olur. dizi[minimum] değeri 9 sayısına denk gelir.
1 2 3 7 9 8
5. Sıralama İşlemi
8 değeri 9'dan küçüktür. Dolayısıyla swap uygulanır.
1 2 3 7 8 9
Peki size bir soru, dizimiz şu anda sıralı halde, ancak algoritma gereği bir adım daha uygulamak zorunda kalırız. Çünkü programlar salaktır, biz onları akıllandırmazsak sıralı olduğu halde bu adımı da uygular. Böylece fazladan bir kere daha çalışmış olur. Hatta 6. adımı da çalıştırıp bakalım.
6. Adım: minimum değeri 1 daha artar, dizi[5] değeri kontrol edilir.
1 2 3 7 8 9
Gördüğünüz üzere dizinin sonraki elemanı bulunmuyor. Yani zaten sıralı olan dizi için 1 adım daha çalıştırdık. Ama bu işi yazılımda kolayca halledebiliriz. Bakın ne zaman sıkıntı çıktı? minimum değeri 5 olduğunda. Peki dizimizin boyutu ne? 6! 6'ya N dersek, min değeri N-1 olduğunda değerlendirme yaptırtmayız olur biter ;)
Kodlar için: Selection Sort Algoritması C Kodu konusuna bakabilirsiniz.
Etiketler: Algoritmalar, seçerek sıralama algoritması, seçerek sıralama örneği, selection sort, selection sort nedir, selection sort örneği, sıralama algoritmaları, Swap nedir
