Seçim Sıralaması: Python Kod Örneği ile açıklanan algoritma

İçindekiler:

Anonim

Seçim Sıralaması nedir?

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

Bu, yerinde sıralama olarak bilinir . Seçim sıralaması, O (n 2 ) zaman karmaşıklığına sahiptir; 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ıralı öğeleri içerirken, ikinci liste sıralanmamış öğeleri içerir.

Varsayılan olarak, sıralı 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 daha sonra sıralı listeye yerleştirilir. Bu işlem, tüm değerler karşılaştırılana ve sıralanana kadar tekrar edilir.

Bu Algoritma eğitiminde şunları öğreneceksiniz:

  • Seçim Sıralaması nedir?
  • Seçimli sıralama nasıl çalışır?
  • Problem tanımı
  • Çözüm (Algoritma)
  • Görsel sunum
  • Python 3 kullanarak Seçim Sıralama Programı
  • Kod Açıklama
  • Seçim Sıralamasının Zaman Karmaşıklığı
  • Seçim sıralaması ne zaman kullanılır?
  • Seçim Sıralamasının Avantajları
  • Seçim Sıralamasının Dezavantajları

Seçimli sıralama 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.

Misal:

  • Örneğin, minimum değerin indeksi 3 ise, indis 3 olan elemanın değeri indeks 0'a, indeks 0'daki değer indeks 3'e yerleştirilir. minimum değer, ardından konumlarını döndürür.
  • Minimum değer olarak belirlenen eleman daha sonra sıralı liste olan sol taraftaki bölüme taşınır.
  • Bölümlenmiş taraf artık bir öğeye sahipken, bölümlenmemiş taraf (n - 1) öğelere sahiptir; burada n, listedeki öğelerin toplam sayısıdır. Bu işlem, tüm öğeler değerlerine göre karşılaştırılıp sıralanana kadar tekrar tekrar tekrarlanır.

Problem tanımı

Rastgele sırada olan öğeler listesinin artan sırada sıralanması gerekir. Aşağıdaki listeyi bir örnek olarak düşünün.

[21,6,9,33,3]

Yukarıdaki liste, aşağıdaki sonuçları elde etmek için sıralanmalıdır.

[3,6,9,21,33]

Çözüm (Algoritma)

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

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

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

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

Görsel sunum

Beş öğeden oluşan bir liste verildiğinde, aşağıdaki resimler, seçim sıralama algoritmasının bunları sıralarken değerleri nasıl yinelediğini gösterir.

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

Aşama 1)

Birinci değer 21, minimum değer olup olmadığını kontrol etmek için değerlerin geri kalanıyla karşılaştırılır.

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

Adım 2)

Sıralanmamış bölümdeki ilk öğe olan 6 değeri, daha düşük bir değerin var olup olmadığını bulmak için değerlerin geri kalanıyla karşılaştırılır.

6 değeri minimum değerdir, bu nedenle konumunu korur.

Aşama 3)

Sıralanmamış listenin 9 değerine sahip ilk öğesi, minimum değer olup olmadığını kontrol etmek için değerlerin geri kalanıyla karşılaştırılır.

9 değeri minimum değerdir, bu nedenle sıralanan bölümdeki konumunu korur.

Adım 4)

33 değeri, değerlerin geri kalanıyla karşılaştırılır.

21 değeri 33'ten düşüktür, bu nedenle yukarıdaki yeni listeyi oluşturmak için pozisyonlar değiştirilir.

Adım 5)

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

Son liste yukarıdaki resimde gösterilen gibidir.

Python 3 kullanarak Seçim Sıralama Programı

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

def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))

Yukarıdaki kodu çalıştırın aşağıdaki sonuçları verir

[3, 6, 9, 21, 33]

Kod Açıklama

Kodun açıklaması aşağıdaki gibidir

İş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ğerlerini yinelemek için döngüyü kullanır. Yineleme sayısı (n - 1). N'nin değeri 5, yani (5-1) bize 4 verir. Bu, dış yinelemelerin 4 kez gerçekleştirileceği anlamına gelir. Her yinelemede, i değişkeninin değeri minValueIndex değişkenine atanır.
  4. İç döngü. Döngüyü, en soldaki değeri sağ taraftaki diğer değerlerle karşılaştırmak için kullanır. Ancak, j değeri 0 dizininde başlamaz. (İ + 1) 'den başlar. Bu, daha önceden sıralanmamış öğelere odaklanmamız için önceden sıralanmış değerleri hariç tutar.
  5. Sıralanmamış listede minimum değeri bulur ve uygun konumuna yerleştirir
  6. Takas koşulu doğru olduğunda minValueIndex değerini günceller
  7. Eşit olup olmadıklarını görmek için minValueIndex ve i dizin numaralarının değerlerini karşılaştırır
  8. En soldaki değer geçici bir değişkende saklanır
  9. Sağ taraftan daha düşük olan değer, ilk pozisyonu alır
  10. Geçici değerde saklanan değer, daha önce minimum değer tarafından tutulan pozisyonda saklanır.
  11. Sıralanan listeyi işlev sonucu olarak verir
  12. Rastgele sayılar içeren bir liste oluşturur
  13. Parametre olarak el içinde geçen Sıralama işlevini seçip çağırdıktan sonra sıralanan 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 sürelerinin 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 yürütülür, burada n, listedeki toplam değer sayısıdır.

Dış döngüden gelen değeri değerlerin geri kalanıyla karşılaştıran iç döngü de n kez yürütülür, burada n listedeki toplam öğe sayısıdır.

Bu nedenle, yürütme sayısı (n * n) 'dir ve bu aynı zamanda O (n 2 ) olarak da ifade edilebilir .

Seçim sıralaması üç karmaşıklık kategorisine sahiptir:

  • En kötü durum - bu, sağlanan listenin azalan sırada olduğu yerdir. Algoritma, [Big-O] O (n 2 ) olarak ifade edilen maksimum yürütme sayısını gerçekleştirir.
  • En iyi durum - bu, sağlanan liste zaten sıralandığında ortaya çıkar. Algoritma, [Big-Omega] Ω (n 2 ) olarak ifade edilen minimum yürütme sayısını gerçekleştirir.
  • Ortalama durum - bu, liste rastgele sırada olduğunda ortaya çıkar. Ortalama karmaşıklık [Büyük-teta] ⊝ (n 2 ) olarak ifade edilir.

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

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

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

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

Seçim Sıralamasının Avantajları

Aşağıdakiler, seçim sıralamasının avantajlarıdır

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

Seçim Sıralamasının Dezavantajları

Aşağıdakiler, seçim sıralamasının dezavantajlarıdır.

  • Büyük listelerde çalışırken kötü performans gösteriyor.
  • Sıralama sırasında yapılan yineleme sayısı n karedir; burada n, listedeki öğelerin toplam sayısıdır.
  • Hızlı sıralama gibi diğer algoritmalar, seçim sıralamasına kıyasla daha iyi performansa sahiptir.

Özet:

  • Seçim sıralaması, rastgele bir listeyi sıralı bir liste halinde sıralamak için kullanılan yerinde bir karşılaştırma algoritmasıdır. Zaman karmaşıklığı O (n 2 )
  • Liste, sıralı ve sıralanmamış olarak iki bölüme ayrılmıştır. Minimum değer, sıralanmamış bölümden seçilir ve sıralı bölüme yerleştirilir.
  • Bu şey, tüm öğeler sıralanana kadar tekrar edilir.
  • Sözde kodu Python 3'te uygulamak, iki for döngüsü kullanmayı ve takasın gerekli olup olmadığını kontrol etmek için ifadelerin kullanılmasını içerir.
  • Zaman karmaşıklığı, listeyi sıralamak için gereken adımların sayısını ölçer.
  • En kötü durum zaman karmaşıklığı, liste azalan sırada olduğunda ortaya çıkar. Zaman karmaşıklığı [Big-O] O (n 2 )
  • En iyi durum zaman karmaşıklığı, liste zaten artan sırada olduğunda gerçekleşir. Zaman karmaşıklığı [Big-Omega] Ω (n 2 )
  • Ortalama durum zaman karmaşıklığı, liste rastgele sırada olduğunda gerçekleşir. Zaman karmaşıklığı [Big-theta] ⊝ (n 2 )
  • Seçim sıralaması, sıralanacak küçük bir öğe listeniz olduğunda, değerlerin değiş tokuşunun 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çim sıralamasıyla karşılaştırıldığında daha iyi performansa sahiptir.