DAA - Seçim Sıralaması

Bu tür sıralamaya Selection Sortöğeleri tekrar tekrar sıralayarak çalıştığı için. Şu şekilde çalışır: ilk önce dizideki en küçük olanı bulun ve onu birinci konumdaki elemanla değiştirin, sonra ikinci en küçük elemanı bulun ve onu ikinci konumdaki elemanla değiştirin ve tüm dizi olana kadar bu şekilde devam edin. sıralandı.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Seçme sıralama, en basit sıralama tekniklerinden biridir ve küçük dosyalar için çok iyi çalışır. Her bir öğe aslında en fazla bir kez taşındığından oldukça önemli bir uygulamaya sahiptir.

Bölüm sıralama, dosyaları çok büyük nesneler (kayıtlar) ve küçük anahtarlarla sıralamak için tercih edilen bir yöntemdir. En kötü durum, dizi zaten azalan bir düzende sıralanmışsa ve bunları artan bir düzende sıralamak istiyorsak ortaya çıkar.

Bununla birlikte, seçim sıralama algoritmasının gerektirdiği süre, sıralanacak dizinin orijinal sırasına çok duyarlı değildir: A[j] < min x her durumda tam olarak aynı sayıda yürütülür.

Seçim sıralaması, zamanının çoğunu dizinin sıralanmamış bölümündeki minimum elemanı bulmaya harcar. Seçim sıralaması ve Kabarcık sıralaması arasındaki benzerliği açıkça gösterir.

• Kabarcık sıralama, her aşamada kalan maksimum öğeleri seçer, ancak dizinin sıralanmamış bir kısmına bir düzen vermek için biraz çaba harcar.

• Seçim sıralaması, hem en kötü hem de ortalama durumda ikinci dereceden oluşur ve fazladan bellek gerektirmez.

Her biri için i itibaren 1 -e n - 1bir değişim var ve n - i karşılaştırmalar, yani toplam n - 1 borsalar ve

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 karşılaştırmalar.

Bu gözlemler, girdi verisi ne olursa olsun geçerlidir.

En kötü durumda, bu ikinci dereceden olabilir, ancak ortalama durumda bu miktar O(n log n). İma eder kirunning time of Selection sort is quite insensitive to the input.

Uygulama

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Misal

Unsorted list:

5 2 1 4 3

1 ^st yineleme:

En küçük = 5

2 <5, en küçük = 2

1 <2, en küçük = 1

4> 1, en küçük = 1

3> 1, en küçük = 1

5 ile 1'i değiştirin

1 2 5 4 3

2 ^nd yineleme:

En küçük = 2

2 <5, en küçük = 2

2 <4, en küçük = 2

2 <3, en küçük = 2

Takas Yok

1 2 5 4 3

3 ^rd yineleme:

En küçük = 5

4 <5, en küçük = 4

3 <4, en küçük = 3

5 ve 3'ü değiştirin

1 2 3 4 5

4 ^th yineleme:

En küçük = 4

4 <5, en küçük = 4

Takas Yok

1 2 3 4 5

En sonunda,

the sorted list is

1 2 3 4 5