Seçim Sıralama Algoritması ile Python Code Örnek E-posta

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]

Code açıklama

Kodun açıklaması şu şekilde

İşte Code açıklama:

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. Takas işlemi gerçekleştiğinde minValueIndex değerini günceller.ping koşul doğru
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, verilen listenin zaten sıralı olduğu durumlarda gerçekleşir. Algoritma, [Big-Omega] Ω(n) olarak ifade edilen minimum sayıda çalıştırma gerçekleştirir.²)
• Ortalama durum – bu, listenin rastgele sırada olduğu durumlarda meydana gelir. Ortalama karmaşıklık [Big-theta] Θ(n) olarak ifade edilir.²)

Seçim sıralama algoritmasının alan karmaşıklığı O(1)'dir çünkü takas için kullanılan tek bir zamansal değişkene ihtiyaç duyar.ping değerleri.

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
• Takas maliyetiping değerler önemsizdir
• 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.

SSS