Ordinamento selezione in Java

1. Introduzione

In questo tutorial impareremo l'ordinamento della selezione , ne vedremo l'implementazione in Java e ne analizzeremo le prestazioni.

2. Panoramica dell'algoritmo

L' ordinamento della selezione inizia con l'elemento nella prima posizione di un array non ordinato ed esegue la scansione degli elementi successivi per trovare l'elemento più piccolo . Una volta trovato, l'elemento più piccolo viene scambiato con l'elemento in prima posizione.

L'algoritmo si sposta quindi sull'elemento nella 2a posizione e scansiona gli elementi successivi per trovare l'indice del 2 ° elemento più piccolo. Una volta trovato, il secondo elemento più piccolo viene scambiato con l'elemento in seconda posizione.

Questo processo continua finché non raggiungiamo l'n-1 ° elemento dell'array, che pone l'n-1 ° elemento più piccolo nella n-1a posizione. L'ultimo elemento si posiziona automaticamente, nella n-1a iterazione, ordinando così l'array.

Troviamo l'elemento più grande invece del più piccolo per ordinare l'array in ordine decrescente.

Vediamo un esempio di un array non ordinato e lo ordiniamo in ordine crescente per comprendere visivamente l'algoritmo.

2.1. Un esempio

Considera il seguente array non ordinato:

int [] arr = {5, 4, 1, 6, 2}

Iterazione 1

Considerando il funzionamento dell'algoritmo di cui sopra, iniziamo con l'elemento in 1a posizione - 5 - e scansioniamo tutti gli elementi successivi per trovare l'elemento più piccolo - 1. Quindi scambiamo l'elemento più piccolo con l'elemento in 1a posizione.

L'array modificato ora ha il seguente aspetto:

{1, 4, 5, 6, 2}

Confronti totali effettuati: 4

Iterazione 2

Nella seconda iterazione, passiamo al 2 ° elemento - 4 - e scansioniamo gli elementi successivi per trovare il secondo elemento più piccolo - 2. Quindi scambiamo il secondo elemento più piccolo con l'elemento in 2a posizione.

L'array modificato ora ha il seguente aspetto:

{1, 2, 5, 6, 4}

Totale confronti effettuati: 3

Continuando in modo simile, abbiamo le seguenti iterazioni:

Iterazione 3

{1, 2, 4, 6, 5}

Confronti totali effettuati: 2

Iterazione 4

{1, 2, 4, 5, 6}

Confronti totali effettuati: 1

3. Implementazione

Implementiamo Selection Sort usando un paio di cicli for :

public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j  arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }

Naturalmente, per invertirlo potremmo fare qualcosa di abbastanza simile:

public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }

E con un po 'più di olio di gomito, potremmo combinarli usando Comparator .

4. Panoramica delle prestazioni

4.1. Tempo

Nell'esempio che abbiamo visto in precedenza, la selezione dell'elemento più piccolo richiedeva un totale di (n-1) confronti seguiti da uno scambio nella prima posizione. Allo stesso modo, la selezione dell'elemento più piccolo successivo richiedeva confronti totali (n-2) seguiti dallo scambio in seconda posizione e così via.

Quindi, a partire dall'indice 0, eseguiamo n-1, n-2, n-3, n-4…. 1 confronti. L'ultimo elemento si posiziona automaticamente a causa di iterazioni e scambi precedenti.

Matematicamente, la somma dei primi n-1 numeri naturali ci dirà di quanti confronti abbiamo bisogno per ordinare un array di dimensione n usando l' ordinamento della selezione.

La formula per la somma di n numeri naturali è n (n + 1) / 2 .

Nel nostro caso, abbiamo bisogno della somma dei primi n-1 numeri naturali. Pertanto, sostituiamo n con n-1 nella formula sopra per ottenere:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Poiché n ^ 2 cresce in modo prominente al crescere di n , consideriamo la maggiore potenza di n come benchmark delle prestazioni, facendo in modo che questo algoritmo abbia una complessità temporale di O (n ^ 2).

4.2. Spazio

In termini di complessità dello spazio ausiliario, l'ordinamento della selezione richiede una variabile aggiuntiva per mantenere temporaneamente il valore per lo scambio. Pertanto, la complessità dello spazio di Selection Sort è O (1) .

5. conclusione

L'ordinamento della selezione è un algoritmo di ordinamento molto semplice da comprendere e implementare. Sfortunatamente, la sua complessità temporale quadratica lo rende una tecnica di smistamento costosa . Inoltre, poiché l'algoritmo deve scansionare ogni elemento, la complessità temporale del caso migliore , del caso medio e del caso peggiore è la stessa .

Anche altre tecniche di ordinamento come Insertion Sort e Shell Sort hanno una complessità temporale quadratica nel caso peggiore, ma funzionano meglio nei casi migliori e medi.

Controlla il codice completo per l'ordinamento della selezione su GitHub.