Menü

Örneklerle C ++ 'da Seçim Sırala

  • Ana
  • Diğer
  • Örneklerle C ++ 'da Seçim Sırala

selection sort c with examples

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Örneklerle C ++ 'da Seçime Derinlemesine Bir Bakış.

Adından da anlaşılacağı gibi, seçim sıralama tekniği önce dizideki en küçük öğeyi seçer ve onu dizideki ilk öğe ile değiştirir.

Ardından, dizideki en küçük ikinci öğeyi ikinci öğe ile değiştirir ve bu böyle devam eder. Böylece her geçişte dizideki en küçük öğe seçilir ve tüm dizi sıralanana kadar uygun konumuna yerleştirilir.

=> Mükemmel C ++ Eğitim Kılavuzuna Buradan Göz Atın.

Seçim Sıralaması

Ne öğreneceksin:

Giriş

Teknik, her geçişte yalnızca en küçük öğeyi bulup doğru konuma yerleştirmeyi içerdiğinden, seçim sıralaması oldukça basit bir sıralama tekniğidir.

Sıralanacak liste küçük boyutta olduğunda seçim sıralaması verimli bir şekilde çalışır, ancak sıralanacak liste boyutu büyüdükçe performansı kötü bir şekilde etkilenir.

Bu nedenle, seçim sıralamanın daha büyük veri listeleri için tavsiye edilmediğini söyleyebiliriz.

Genel Algoritma

Seçim sıralaması için Genel Algoritma aşağıda verilmiştir:

.jar dosyasını açan nedir

Seçim Sıralaması (A, N)

Aşama 1 : K = 1 - N-1 için Adım 2 ve 3'ü tekrarlayın
Adım 2 : Çağrı rutini en küçük (A, K, N, POS)
Aşama 3 : A (K) ile A (POS) arasında yer değiştirin
(Döngünün sonu)
4. adım : ÇIKIŞ

Rutin en küçük (A, K, N, POS)

  • Aşama 1 : (başlat) smallestElem = A (K) olarak ayarlayın
  • Adım 2 : (başlat) POS = K ayarla
  • Aşama 3 : J = K + 1 ila N -1 için tekrarlayın
    en küçükElem> A (J) ise
    smallestElem = A (J) olarak ayarlayın
    POS = J ayarla
    (eğer biterse)
    (Döngünün sonu)
  • 4. adım : POS'a dönüş

Seçim Sıralaması İçin Sözde Kod

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

Bu seçim sıralama algoritmasını gösteren bir örnek aşağıda gösterilmiştir.

İllüstrasyon

Seçimi Sırala Çizim

Geçiş2

Geçer3

Geçiş4

Bu resim için tablo halindeki temsili aşağıda gösterilmiştir:

Sıralanmamış listeEn az öğeSıralanmış liste
{18,10,7,20,2}iki{}
{18,10,7,20}7{iki}
{18,10,20}10{2.7}
{18.20}18{2,7,10)
{yirmi}yirmi{2,7,10,18}
{}{2,7,10,18,20}

Çizimden, her geçişte bir sonraki en küçük elemanın sıralanmış dizide doğru konumuna yerleştirildiğini görüyoruz. Yukarıdaki resimden, 5 öğelik bir diziyi sıralamak için dört geçişin gerekli olduğunu görüyoruz. Bu, genel olarak, N elemanlı bir diziyi sıralamak için toplamda N-1 geçişine ihtiyacımız olduğu anlamına gelir.

Aşağıda, C ++ 'da seçim sıralama algoritmasının uygulanması verilmiştir.

C ++ Örneği

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

Çıktı:

Sıralanacak öğelerin giriş listesi

11 5 2 20 42 53 23 34101 22

Sıralı eleman listesi

2 5 11 20 22 23 34 42 53101

Diziyi sıralamak için gereken geçiş sayısı: 10

Yukarıdaki programda gösterildiği gibi, dizideki ilk öğeyi dizideki diğer tüm öğelerle karşılaştırarak seçim sıralamasına başlarız. Bu karşılaştırmanın sonunda dizideki en küçük eleman ilk konuma yerleştirilir.

Bir sonraki geçişte, aynı yaklaşımı kullanarak, dizideki bir sonraki en küçük eleman doğru konumuna yerleştirilir. Bu, N öğeye kadar veya tüm dizi sıralanana kadar devam eder.

Java Örneği

Daha sonra, Java dilinde seçim sıralama tekniğini uyguluyoruz.

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

Çıktı:

Sıralanacak giriş listesi…

11 5 2 20 42 53 23 34101 22

sıralanmış öğeler yazdırılıyor…

2 5 11 20 22 23 34 42 53101

Yukarıdaki java örneğinde de aynı mantığı uyguluyoruz. Dizideki en küçük elemanı tekrar tekrar buluruz ve tüm dizi tamamen sıralanana kadar onu sıralanmış diziye koyarız.

Bu nedenle, seçim sıralaması, dizideki bir sonraki en küçük öğeyi tekrar tekrar bulmamız ve uygun konumundaki öğeyle değiştirmemiz gerektiğinden, uygulanacak en basit algoritmadır.

Seçim Sıralamasının Karmaşıklık Analizi

Yukarıdaki seçim sıralaması için sözde kodda görüldüğü gibi, seçim sıralamanın birbiriyle iç içe geçmiş iki döngü için kendini tamamlaması gerektiğini biliyoruz. Bir for döngüsü, dizideki tüm öğeler arasında ilerler ve minimum öğe indisini, dış for döngüsünün içine yerleştirilmiş başka bir for döngüsü kullanarak buluruz.

Bu nedenle, girdi dizisinin bir N boyutu verildiğinde, seçim sıralama algoritması aşağıdaki zaman ve karmaşıklık değerlerine sahiptir.

En kötü durum zaman karmaşıklığıO (n2); O (n) takas
En iyi vaka süresi karmaşıklığıO (n2); O (n) takas
Ortalama zaman karmaşıklığıO (n2); O (n) takas
Uzay karmaşıklığıO (1)

O'nun zaman karmaşıklığı ( n iki) esas olarak iki döngü için kullanımdan kaynaklanmaktadır. Seçme sıralama tekniğinin hiçbir zaman O (n) takaslarından fazlasını almadığına ve bellek yazma işleminin maliyetli olduğu kanıtlandığında yararlı olduğuna dikkat edin.

Sonuç

Seçimli sıralama, kolayca uygulanabilen bir başka basit sıralama tekniğidir. Seçim sıralaması, sıralanacak değerlerin aralığı bilindiğinde en iyi sonucu verir. Bu nedenle, seçim sıralaması kullanılarak veri yapılarının sıralanması söz konusu olduğunda, yalnızca doğrusal ve sonlu boyutlu veri yapısını sıralayabiliriz.

Bu, seçim sıralamasını kullanarak diziler gibi veri yapılarını verimli bir şekilde sıralayabileceğimiz anlamına gelir.

Bu eğitimde, C ++ ve Java dilleri kullanılarak seçim sıralaması uygulaması dahil olmak üzere seçim sıralamayı ayrıntılı olarak tartıştık. Seçim sıralamasının ardındaki mantık, listedeki en küçük öğeyi tekrar tekrar bulmak ve onu uygun konuma yerleştirmektir.

Bir sonraki eğitimde, şimdiye kadar tartıştığımız diğer iki teknikten daha verimli bir teknik olduğu söylenen ekleme sıralaması hakkında ayrıntılı olarak bilgi edineceğiz, yani kabarcık sıralama ve seçim sıralaması.

=> Burada C ++ Eğitim Öğreticilerinin A-Z'sini Görmek İçin Burayı Kontrol Edin.

Önerilen Kaynaklar

^