DAA - Sortir Pilihan

Jenis pengurutan ini disebut Selection Sortkarena berfungsi dengan mengurutkan elemen berulang kali. Cara kerjanya sebagai berikut: pertama temukan yang terkecil dalam array dan tukarkan dengan elemen di posisi pertama, lalu temukan elemen terkecil kedua dan tukarkan dengan elemen di posisi kedua, dan lanjutkan dengan cara ini hingga seluruh array menjadi diurutkan.

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

Sortir pilihan adalah salah satu teknik pengurutan yang paling sederhana dan berfungsi sangat baik untuk file kecil. Ini memiliki aplikasi yang cukup penting karena setiap item sebenarnya paling banyak dipindahkan satu kali.

Bagian sortir adalah metode pilihan untuk menyortir file dengan objek (record) yang sangat besar dan kunci kecil. Kasus terburuk terjadi jika array sudah diurutkan dalam urutan menurun dan kita ingin mengurutkannya dalam urutan naik.

Meskipun demikian, waktu yang diperlukan oleh algoritme pengurutan pilihan tidak terlalu sensitif terhadap urutan asli larik yang akan diurutkan: uji jika A[j] < min x dieksekusi dengan jumlah yang persis sama dalam setiap kasus.

Sortir pilihan menghabiskan sebagian besar waktunya untuk mencoba menemukan elemen minimum di bagian larik yang tidak diurutkan. Ini dengan jelas menunjukkan kesamaan antara Jenis pilihan dan Jenis gelembung.

Jenis gelembung memilih elemen maksimum yang tersisa di setiap tahap, tetapi menyia-nyiakan beberapa upaya untuk menyampaikan beberapa urutan ke bagian array yang tidak disortir.
Jenis pilihan adalah kuadrat baik dalam kasus terburuk dan rata-rata, dan tidak memerlukan memori tambahan.

Untuk setiap i dari 1 untuk n - 1, ada satu pertukaran dan n - i perbandingan, jadi ada total n - 1 pertukaran dan

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 perbandingan.

Pengamatan ini berlaku, tidak peduli apa data inputnya.

Dalam kasus terburuk, ini bisa menjadi kuadrat, tetapi dalam kasus rata-rata, kuantitas ini O(n log n). Ini menyiratkan bahwarunning time of Selection sort is quite insensitive to the input.

Penerapan

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; 
   } 
}