Seçim Sıralaması: Algoritmanın açıklaması Python Kod Örneği

Seçim Sıralaması Nedir?

SEÇİM SIRALAMA rastgele bir öğe listesini artan düzende sıralamak için kullanılan bir karşılaştırma sıralama algoritmasıdır. Karşılaştırma çok fazla ekstra alan gerektirmez. Zamansal değişken için yalnızca bir ekstra bellek alanı gerektirir.

Bu bilinir Yerinde sıralama. Seçim sıralamasının zaman karmaşıklığı O(n)'dir²) burada n listedeki toplam öğe sayısıdır. Zaman karmaşıklığı, listeyi sıralamak için gereken yineleme sayısını ölçer. Liste iki bölüme ayrılmıştır: İlk liste sıralanmış öğeleri içerirken, ikinci liste sıralanmamış öğeleri içerir.

Varsayılan olarak sıralanmış liste boştur ve sıralanmamış liste tüm öğeleri içerir. Sıralanmamış liste daha sonra minimum değer için taranır ve bu daha sonra sıralanmış listeye yerleştirilir. Bu işlem tüm değerler karşılaştırılıp sıralanıncaya kadar tekrarlanır.

Seçim sıralaması nasıl çalışır?

Sıralanmamış bölümdeki ilk öğe, minimum değer olup olmadığını kontrol etmek için sağ taraftaki tüm değerlerle karşılaştırılır. Minimum değer değilse konumu minimum değerle değiştirilir.

Örnek E-posta

• Örneğin, minimum değerin indeksi 3 ise, indeksi 3 olan elemanın değeri indeks 0'a, indeksi 0'daki değer ise indeks 3'e yerleştirilir. Sıralanmamış bölümdeki ilk eleman ise minimum değeri alır ve ardından konumlarını döndürür.
• Minimum değer olarak belirlenen öğe daha sonra sol taraftaki sıralı liste olan bölüme taşınır.
• Bölümlenmiş tarafta artık bir öğe bulunurken, bölümlenmemiş tarafta (n – 1) öğe bulunur; burada n, listedeki toplam öğe sayısıdır. Bu süreç, tüm öğeler karşılaştırılana ve değerlerine göre sıralanana kadar tekrar tekrar tekrarlanır.

Problem tanımı

Rastgele sırada olan bir öğe listesinin artan düzende sıralanması gerekir. Aşağıdaki listeyi bir örnek olarak ele alalım.

[21,6,9,33,3]

Yukarıdaki liste aşağıdaki sonuçları üretecek şekilde sıralanmalıdır

[3,6,9,21,33]

Çözüm (Algoritma)

) 1 Adım Dizinin toplam boyutu olan n değerini alın

) 2 Adım Listeyi sıralanmış ve sıralanmamış bölümlere ayırın. Sıralanmış bölüm başlangıçta boştur, sıralanmamış bölüm ise tüm listeyi içerir

) 3 Adım Bölümlenmemiş bölümden minimum değeri seçin ve sıralanan bölüme yerleştirin.

) 4 Adım Listedeki tüm öğeler sıralanana kadar işlemi (n – 1) kez tekrarlayın.

Görsel sunum

Beş elemandan oluşan bir liste verildiğinde, aşağıdaki görseller seçim sıralama algoritmasının değerleri sıralarken nasıl yineleme yaptığını göstermektedir.

Aşağıdaki görüntü sıralanmamış listeyi göstermektedir

) 1 Adım

İlk değer 21, minimum değer olup olmadığını kontrol etmek için diğer değerlerle karşılaştırılır.

3 minimum değerdir, dolayısıyla 21 ve 3'ün konumları değiştirilir. Yeşil arka plana sahip değerler listenin sıralanmış bölümünü temsil eder.

) 2 Adım

Sıralanmamış bölümün ilk öğesi olan 6 değeri, daha düşük bir değerin olup olmadığını bulmak için diğer değerlerle karşılaştırılır.

6 değeri minimum değer olduğundan konumunu korur.

) 3 Adım

Sıralanmamış listenin 9 değerine sahip ilk elemanı, minimum değer olup olmadığını kontrol etmek için diğer değerlerle karşılaştırılır.

9 değeri minimum değer olduğundan sıralanan bölümdeki konumunu korur.

) 4 Adım

33 değeri diğer değerlerle karşılaştırılır.

21 değeri 33'ten küçüktür, dolayısıyla yukarıdaki yeni listeyi oluşturmak için konumlar değiştirilir.

) 5 Adım

Bölümlenmemiş listede yalnızca bir değerimiz kaldı. Bu nedenle zaten sıralanmıştır.

Son liste yukarıdaki resimde gösterilene benzer.

Seçim Sıralama Programı kullanarak Python 3

Aşağıdaki kod, seçim sıralama uygulamasını kullanarak gösterir Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Yukarıdaki kodu çalıştırmak aşağıdaki sonuçları üretir

[3, 6, 9, 21, 33]

Kod Açıklama

Kodun açıklaması şu şekilde

İşte Kod açıklaması:

1. SelectionSort adlı bir işlevi tanımlar
2. Listedeki toplam öğe sayısını alır. Değerleri karşılaştırırken yapılacak geçiş sayısını belirlemek için buna ihtiyacımız var.
3. Dış döngü. Listenin değerleri arasında yineleme yapmak için döngüyü kullanır. Yineleme sayısı (n – 1). N'nin değeri 5 olduğundan (5 – 1) bize 4 değerini verir. Bu da dış iterasyonların 4 kez yapılacağı anlamına gelir. Her yinelemede, i değişkeninin değeri minValueIndex değişkenine atanır.
4. İç döngü. En soldaki değeri sağ taraftaki diğer değerlerle karşılaştırmak için döngüyü kullanır. Ancak j'nin değeri 0 indeksinden başlamaz. (i+1)'den başlar. Bu, halihazırda sıralanmış olan değerleri hariç tutar, böylece henüz sıralanmamış öğelere odaklanırız.
5. Sıralanmamış listedeki minimum değeri bulur ve uygun konuma yerleştirir
6. Değiştirme koşulu doğru olduğunda minValueIndex'in değerini günceller
7. MinValueIndex ve i indeks numaralarının değerlerini karşılaştırarak eşit olup olmadıklarını kontrol eder
8. En soldaki değer geçici bir değişkende saklanır
9. Sağ taraftan daha düşük olan değer ilk sırayı alır
10. Zamansal değerde saklanan değer, daha önce minimum değerin tuttuğu pozisyonda saklanır
11. İşlev sonucu olarak sıralanmış listeyi döndürür
12. Rastgele sayılara sahip bir liste oluşturur
13. Parametre olarak el'i geçen Sıralama işlevi seçimini çağırdıktan sonra sıralanmış listeyi yazdırın.

Seçim Sıralamasının Zaman Karmaşıklığı

Sıralama karmaşıklığı, listeyi sıralamak için gereken yürütme zamanlarının sayısını ifade etmek için kullanılır. Uygulamanın iki döngüsü vardır.

Listeden değerleri birer birer seçen dış döngü n kez çalıştırılır; burada n, listedeki toplam değer sayısıdır.

Dış döngüdeki değeri diğer değerlerle karşılaştıran iç döngü de n defa yürütülür, burada n listedeki toplam eleman sayısını ifade eder.

Bu nedenle yürütme sayısı (n * n) olup, O(n) olarak da ifade edilebilir.²).

Seçim sıralaması karmaşıklık açısından üç kategoriye ayrılır;

• En kötü durumda – sağlanan listenin azalan sırada olduğu yer burasıdır. Algoritma, [Big-O] O(n) olarak ifade edilen maksimum yürütme sayısını gerçekleştirir.²)
• En iyi senaryo – bu, sağlanan liste zaten sıralanmış olduğunda gerçekleşir. Algoritma, [Big-Omega] ?(n olarak ifade edilen minimum yürütme sayısını gerçekleştirir²)
• Ortalama durum – bu, liste rastgele sırada olduğunda meydana gelir. Ortalama karmaşıklık [Büyük-teta] ?(n olarak ifade edilir²)

Seçim sıralaması, değerleri değiştirmek için kullanılan bir zamansal değişken gerektirdiğinden O(1) uzay karmaşıklığına sahiptir.

Seçim sıralaması ne zaman kullanılır?

Seçim sıralaması aşağıdakileri yapmak istediğinizde en iyi şekilde kullanılır:

• Küçük bir öğe listesini artan düzende sıralamanız gerekir
• Değerleri değiştirmenin maliyeti önemsiz olduğunda
• Ayrıca listedeki tüm değerlerin kontrol edildiğinden emin olmanız gerektiğinde de kullanılır.

Seçimli Sıralamanın Avantajları

Seçim sıralamasının avantajları şunlardır:

• Küçük listelerde çok iyi performans gösteriyor
• Yerinde bir algoritmadır. Sıralama için çok fazla alana ihtiyaç duymaz. Zamansal değişkeni tutmak için yalnızca bir ekstra alan gereklidir.
• Zaten sıralanmış öğeler üzerinde iyi performans gösterir.

Seçimli Sıralamanın Dezavantajları

Seçmeli sıralama yönteminin dezavantajları şunlardır.

• Büyük listeler üzerinde çalışırken düşük performans gösteriyor.
• Sıralama sırasında yapılan yinelemelerin sayısı n-karedir; burada n, listedeki toplam öğe sayısıdır.
• Hızlı sıralama gibi diğer algoritmalar, seçimli sıralamaya kıyasla daha iyi performansa sahiptir.

ÖZET

• Seçim sıralaması, rastgele bir listeyi sıralı bir listeye sıralamak için kullanılan yerinde karşılaştırma algoritmasıdır. Zaman karmaşıklığı O(n)'dir.²)
• Liste sıralı ve sıralanmamış olmak üzere iki bölüme ayrılmıştır. Sıralanmamış bölümden minimum değer seçilir ve sıralanmış bölüme yerleştirilir.
• Bu şey, tüm öğeler sıralanana kadar tekrarlanır.
• Sahte kodun uygulanması Python 3, takasın gerekli olup olmadığını kontrol etmek için iki for döngüsü ve if ifadesinin kullanılmasını içerir
• Zaman karmaşıklığı, listeyi sıralamak için gereken adım sayısını ölçer.
• En kötü durum zaman karmaşıklığı, liste azalan sırada olduğunda meydana gelir. [Büyük-O] O(n) zaman karmaşıklığına sahiptir²)
• En iyi durum zaman karmaşıklığı, liste zaten artan sırada olduğunda gerçekleşir. [Büyük-Omega] ?(n zaman karmaşıklığına sahiptir²)
• Ortalama durum zaman karmaşıklığı, liste rastgele sırada olduğunda gerçekleşir. [Büyük-teta] ?(n zaman karmaşıklığına sahiptir²)
• Seçimli sıralama, sıralanacak küçük bir öğe listeniz olduğunda, değerleri değiştirmenin maliyeti önemli olmadığında ve tüm değerlerin kontrol edilmesi zorunlu olduğunda en iyi şekilde kullanılır.
• Seçim sıralaması büyük listelerde iyi performans göstermiyor
• Hızlı sıralama gibi diğer sıralama algoritmaları, seçimli sıralamayla karşılaştırıldığında daha iyi performansa sahiptir.