DAA - Ordinamento selezione

Questo tipo di ordinamento viene chiamato Selection Sortpoiché funziona ordinando ripetutamente gli elementi. Funziona come segue: prima trova il più piccolo nell'array e scambialo con l'elemento nella prima posizione, quindi trova il secondo elemento più piccolo e scambialo con l'elemento nella seconda posizione, e continua in questo modo fino a quando l'intero array è smistato.

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

L'ordinamento di selezione è una delle tecniche di ordinamento più semplici e funziona molto bene per file di piccole dimensioni. Ha un'applicazione abbastanza importante in quanto ogni elemento viene effettivamente spostato al massimo una volta.

L'ordinamento di sezione è un metodo di scelta per ordinare i file con oggetti molto grandi (record) e chiavi piccole. Il caso peggiore si verifica se l'array è già ordinato in ordine decrescente e vogliamo ordinarlo in ordine crescente.

Tuttavia, il tempo richiesto dall'algoritmo di ordinamento della selezione non è molto sensibile all'ordine originale dell'array da ordinare: il test se A[j] < min x viene eseguito esattamente lo stesso numero di volte in ogni caso.

L'ordinamento della selezione trascorre la maggior parte del tempo cercando di trovare l'elemento minimo nella parte non ordinata dell'array. Mostra chiaramente la somiglianza tra l'ordinamento di selezione e l'ordinamento a bolle.

  • Bubble sort seleziona il numero massimo di elementi rimanenti in ogni fase, ma spreca un po 'di sforzo nell'impartire un po' di ordine a una parte non ordinata dell'array.

  • L'ordinamento della selezione è quadratico sia nel caso peggiore che in quello medio e non richiede memoria aggiuntiva.

Per ciascuno i a partire dal 1 per n - 1, c'è uno scambio e n - i confronti, quindi c'è un totale di n - 1 scambi e

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

Queste osservazioni valgono, indipendentemente dai dati di input.

Nel caso peggiore, questo potrebbe essere quadratico, ma nel caso medio, questa quantità lo è O(n log n). Ciò implica che ilrunning time of Selection sort is quite insensitive to the input.

Implementazione

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

Esempio

Unsorted list:
5 2 1 4 3

1 ° di iterazione:

Minimo = 5

2 <5, il più piccolo = 2

1 <2, il più piccolo = 1

4> 1, più piccolo = 1

3> 1, più piccolo = 1

Scambia 5 e 1
1 2 5 4 3

2 ° iterazione:

Minimo = 2

2 <5, il più piccolo = 2

2 <4, il più piccolo = 2

2 <3, il più piccolo = 2

Nessuno scambio
1 2 5 4 3

3 rd iterazione:

Minimo = 5

4 <5, il più piccolo = 4

3 <4, il più piccolo = 3

Scambia 5 e 3
1 2 3 4 5

4 th iterazione:

Minimo = 4

4 <5, il più piccolo = 4

Nessuno scambio
1 2 3 4 5

Finalmente,

the sorted list is
1 2 3 4 5