L'ordinamento per inserimento e l'ordinamento per selezione sono due algoritmi di ordinamento popolari e la loro differenza principale risiede nel modo in cui selezionano e posizionano gli elementi in una sequenza ordinata.
Ordinamento della selezione:
- Nell'ordinamento per selezione, l'array di input è diviso in due parti: una parte ordinata e una parte non ordinata.
- L'algoritmo trova ripetutamente l'elemento minimo nella parte non ordinata e lo scambia con l'elemento più a sinistra della parte non ordinata, espandendo così la parte ordinata di un elemento.
- L'ordinamento della selezione ha una complessità temporale pari a O(n^2) in tutti i casi.
Ordinamento di inserimento:
- Nell'ordinamento per inserzione, anche l'array di input è diviso in due parti: una parte ordinata e una parte non ordinata.
L'algoritmo preleva un elemento dalla parte non ordinata e lo colloca nella posizione corretta nella parte ordinata, spostando gli elementi più grandi di una posizione a destra.
L'ordinamento per inserzione ha una complessità temporale di O(n^2) nel caso peggiore, ma può funzionare meglio su array parzialmente ordinati, con una complessità temporale nel migliore dei casi di O(n).
Principali differenze: - L'ordinamento per selezione scansiona la parte non ordinata per trovare l'elemento minimo, mentre l'ordinamento per inserimento scansiona la parte ordinata per trovare la posizione corretta in cui posizionare l'elemento.
L'ordinamento per selezione richiede meno scambi rispetto all'ordinamento per inserzione, ma più confronti.
L'ordinamento per inserimento è più efficiente dell'ordinamento per selezione quando l'array di input è parzialmente ordinato o quasi ordinato, mentre l'ordinamento per selezione funziona meglio quando l'array è altamente disordinato.
In sintesi, entrambi gli algoritmi hanno una complessità temporale simile, ma i loro metodi di selezione e posizionamento differiscono. La scelta tra loro dipende dalle caratteristiche dei dati di input e dai requisiti specifici del problema in questione.
Vantaggi dell'ordinamento per inserzione:
- Semplice e facile da comprendere e implementare.
- Efficiente per set di dati di piccole dimensioni o dati quasi ordinati.
- Algoritmo di ordinamento sul posto, il che significa che non richiede memoria aggiuntiva.
- Algoritmo di ordinamento stabile, ovvero mantiene l'ordine relativo degli elementi uguali nell'array di input.
Svantaggi dell'ordinamento per inserzione:
- Inefficiente per set di dati di grandi dimensioni o dati in ordine inverso, con una complessità temporale nel caso peggiore pari a O (n ^ 2).
- L'ordinamento per inserzione prevede molti scambi, il che può rallentarlo sui computer moderni.
Vantaggi dell'ordinamento della selezione:
- Semplice e facile da comprendere e implementare.
- Efficiente per set di dati di piccole dimensioni o dati quasi ordinati.
- Algoritmo di ordinamento sul posto, il che significa che non richiede memoria aggiuntiva.
Svantaggi dell'ordinamento della selezione:
- Inefficiente per set di dati di grandi dimensioni, con una complessità temporale nel caso peggiore pari a O (n ^ 2).
- L'ordinamento di selezione prevede molti confronti, il che può renderlo lento sui computer moderni.
- Algoritmo di ordinamento instabile, il che significa che potrebbe non mantenere l'ordine relativo degli elementi uguali nell'array di input.
In questo articolo discuteremo la differenza tra l'ordinamento di inserzione e l'ordinamento di selezione:
Ordinamento di inserimento è un semplice algoritmo di ordinamento che funziona in modo simile al modo in cui ordini le carte da gioco che hai in mano. L'array è virtualmente suddiviso in una parte ordinata e una non ordinata. I valori della parte non ordinata vengono selezionati e posizionati nella posizione corretta nella parte ordinata.
Algoritmo:
Per ordinare un array di dimensione n in ordine crescente:
- Itera da arr[1] a arr[n] sull'array.
- Confronta l'elemento corrente (chiave) con il suo predecessore.
- Se l'elemento chiave è più piccolo del suo predecessore, confrontalo con gli elementi precedenti. Sposta gli elementi maggiori di una posizione verso l'alto per fare spazio all'elemento scambiato.
Di seguito è riportata l'immagine per illustrare l'ordinamento di inserimento:
Di seguito è riportato il programma dello stesso:
C++
// C++ program for the insertion sort> #include> using> namespace> std;> // Function to sort an array using> // insertion sort> void> insertionSort(>int> arr[],>int> n)> {> >int> i, key, j;> >for> (i = 1; i key = arr[i]; j = i - 1; // Move elements of arr[0..i-1], // that are greater than key to // one position ahead of their // current position while (j>= 0 && arr[j]> tasto) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = chiave; } } // Funzione per stampare un array di dimensione N void printArray(int arr[], int n) { int i; // Stampa l'array for (i = 0; i cout<< arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[] = { 12, 11, 13, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call insertionSort(arr, N); printArray(arr, N); return 0; }> |
>
>
Giava
// Java program for the above approach> import> java.util.*;> class> GFG> {> > // Function to sort an array using> // insertion sort> static> void> insertionSort(>int> arr[],>int> n)> {> >int> i, key, j;> >for> (i =>1>; i { key = arr[i]; j = i - 1; // Move elements of arr[0..i-1], // that are greater than key to // one position ahead of their // current position while (j>= 0 && arr[j]> tasto) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = chiave; } } // Funzione per stampare un array di dimensione N static void printArray(int arr[], int n) { int i; // Stampa l'array for (i = 0; i System.out.print(arr[i] + ' '); } System.out.println(); } // Codice driver public static void main(String[ ] args) { int arr[] = { 12, 11, 13, 5, 6 }; int N = arr.length; // Chiamata della funzione insertSort(arr, N); printArray(arr, N); Questo codice è fornito da code_hunt.> |
>
>
Python3
# Python 3 program for the insertion sort> # Function to sort an array using> # insertion sort> def> insertionSort(arr, n):> >i>=> 0> >key>=> 0> >j>=> 0> >for> i>in> range>(>1>,n,>1>):> >key>=> arr[i]> >j>=> i>-> 1> ># Move elements of arr[0..i-1],> ># that are greater than key to> ># one position ahead of their> ># current position> >while> (j>>=> 0> and> arr[j]>tasto):> >arr[j>+> 1>]>=> arr[j]> >j>=> j>-> 1> >arr[j>+> 1>]>=> key> # Function to print an array of size N> def> printArray(arr, n):> >i>=> 0> ># Print the array> >for> i>in> range>(n):> >print>(arr[i],end>=> ' '>)> >print>(>'
'>,end>=> '')> # Driver Code> if> __name__>=>=> '__main__'>:> >arr>=> [>12>,>11>,>13>,>5>,>6>]> >N>=> len>(arr)> ># Function Call> >insertionSort(arr, N)> >printArray(arr, N)> > ># This code is contributed by bgangwar59.> |
>
>
C#
// C# program for the above approach> using> System;> class> GFG> {> >// Function to sort an array using> >// insertion sort> >static> void> insertionSort(>int>[] arr,>int> n)> >{> >int> i, key, j;> >for> (i = 1; i { key = arr[i]; j = i - 1; // Move elements of arr[0..i-1], // that are greater than key to // one position ahead of their // current position while (j>= 0 && arr[j]> tasto) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = chiave; } } // Funzione per stampare un array di dimensione N static void printArray(int[] arr, int n) { int i; // Stampa l'array for (i = 0; i { Console.Write(arr[i] + ' '); } Console.WriteLine(); } // Codice driver static public void Main() { int[] arr = new int[] { 12, 11, 13, 5, 6 }; int N = arr.Length; // Chiamata della funzione insertSort(arr, N); printArray(arr, N); contributo di Dharanendra L V> |
>
>
Javascript
> // JavaScript program for the above approach> // Function to sort an array using> // insertion sort> function> insertionSort(arr,n)> {> >let i, key, j;> >for> (i = 1; i { key = arr[i]; j = i - 1; // Move elements of arr[0..i-1], // that are greater than key to // one position ahead of their // current position while (j>= 0 && arr[j]> tasto) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = chiave; } } // Funzione per stampare un array di dimensione N function printArray(arr,n) { let i; // Stampa l'array for (i = 0; i document.write(arr[i] + ' '); } document.write(' '); } // Codice driver let arr=[12, 11 , 13, 5, 6]; let N = arr.length; // Chiamata della funzione insertSort(arr, N); printArray(arr, N); // Questo codice è fornito da avanitrachhadiya2155> |
>
>Produzione:
5 6 11 12 13>
IL ordinamento della selezione L'algoritmo ordina un array trovando ripetutamente l'elemento minimo (considerando l'ordine crescente) dalla parte non ordinata e ponendolo all'inizio. L'algoritmo mantiene due sottoarray in un dato array.
- Il sottoarray è già ordinato.
- Il sottoarray rimanente non è ordinato.
In ogni iterazione dell'ordinamento di selezione, l'elemento minimo (considerando l'ordine crescente) dal sottoarray non ordinato viene selezionato e spostato nel sottoarray ordinato.
Di seguito è riportato un esempio che spiega i passaggi precedenti:
arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64>
Di seguito è riportato il programma dello stesso:
C++
// C++ program for implementation of> // selection sort> #include> using> namespace> std;> // Function to swap two number> void> swap(>int>* xp,>int>* yp)> {> >int> temp = *xp;> >*xp = *yp;> >*yp = temp;> }> // Function to implement the selection> // sort> void> selectionSort(>int> arr[],>int> n)> {> >int> i, j, min_idx;> >// One by one move boundary of> >// unsorted subarray> >for> (i = 0; i // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element swap(&arr[min_idx], &arr[i]); } } // Function to print an array void printArray(int arr[], int size) { int i; for (i = 0; i cout << arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[] = { 64, 25, 12, 22, 11 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call selectionSort(arr, n); cout << 'Sorted array:
'; // Print the array printArray(arr, n); return 0; }> |
>
>
Giava
// Java program for implementation of> // selection sort> import> java.util.*;> class> GFG> {> // Function to implement the selection> // sort> static> void> selectionSort(>int> arr[],>int> n)> {> >int> i, j, min_idx;> >// One by one move boundary of> >// unsorted subarray> >for> (i =>0>; i 1; i++) { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element int temp = arr[min_idx]; arr[min_idx]= arr[i]; arr[i] = temp; } } // Function to print an array static void printArray(int arr[], int size) { int i; for (i = 0; i System.out.print(arr[i]+ ' '); } System.out.println(); } // Driver Code public static void main(String[] args) { int arr[] = { 64, 25, 12, 22, 11 }; int n = arr.length; // Function Call selectionSort(arr, n); System.out.print('Sorted array:
'); // Print the array printArray(arr, n); } } // This code is contributed by aashish1995> |
>
>
Python3
# Python3 program for implementation of> # selection sort> # Function to implement the selection> # sort> def> selectionSort(arr, n):> ># One by one move boundary of> ># unsorted subarray> >for> i>in> range>(n>-> 1>):> ># Find the minimum element> ># in unsorted array> >min_idx>=> i> >for> j>in> range>(i>+> 1>, n):> >if> (arr[j] min_idx = j # Swap the found minimum element # with the first element arr[min_idx], arr[i] = arr[i], arr[min_idx] # Function to print an array def printArray(arr, size): for i in range(size): print(arr[i], end = ' ') print() # Driver Code if __name__ == '__main__': arr = [64, 25, 12, 22, 11] n = len(arr) # Function Call selectionSort(arr, n) print('Sorted array: ') # Print the array printArray(arr, n) # This code is contributed by ukasp> |
>
>
C#
oggetto Java
// C# program for implementation of> // selection sort> using> System;> public> class> GFG> {> // Function to implement the selection> // sort> static> void> selectionSort(>int> []arr,>int> n)> {> >int> i, j, min_idx;> >// One by one move boundary of> >// unsorted subarray> >for> (i = 0; i { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element int temp = arr[min_idx]; arr[min_idx]= arr[i]; arr[i] = temp; } } // Function to print an array static void printArray(int []arr, int size) { int i; for (i = 0; i Console.Write(arr[i]+ ' '); } Console.WriteLine(); } // Driver Code public static void Main(String[] args) { int []arr = { 64, 25, 12, 22, 11 }; int n = arr.Length; // Function Call selectionSort(arr, n); Console.Write('Sorted array:
'); // Print the array printArray(arr, n); } } // This code is contributed by gauravrajput1> |
>
>
Javascript
> // Javascript program for implementation of> // selection sort> // Function to implement the selection> // sort> function> selectionSort(arr, n)> {> >let i, j, min_idx;> > >// One by one move boundary of> >// unsorted subarray> >for>(i = 0; i { // Find the minimum element // in unsorted array min_idx = i; for(j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element let temp = arr[min_idx]; arr[min_idx]= arr[i]; arr[i] = temp; } } // Function to print an array function printArray(arr, size) { let i; for(i = 0; i { document.write(arr[i] + ' '); } document.write(' '); } // Driver Code let arr = [ 64, 25, 12, 22, 11 ]; let n = arr.length; // Function Call selectionSort(arr, n); document.write('Sorted array: '); // Print the array printArray(arr, n); // This code is contributed by rag2127> |
>
>Produzione:
Sorted array: 11 12 22 25 64>
Differenza tabellare tra ordinamento di inserimento e ordinamento di selezione:
| Ordinamento per inserimento | Ordinamento selezione | |
|---|---|---|
| 1. | Inserisce il valore nell'array preordinato per ordinare l'insieme di valori nell'array. | Trova il numero minimo/massimo dall'elenco e ordinalo in ordine crescente/discendente. |
| 2. | È un algoritmo di ordinamento stabile. | È un algoritmo di ordinamento instabile. |
| 3. | La complessità temporale nel caso migliore è Ω(N) quando l'array è già in ordine crescente. Ha Θ(N2) nel caso peggiore e nel caso medio. | Per il caso migliore, il caso peggiore e l'ordinamento di selezione medio hanno complessità Θ(N2). |
| 4. | Il numero di operazioni di confronto eseguite in questo algoritmo di ordinamento è inferiore allo scambio eseguito. | Il numero di operazioni di confronto eseguite in questo algoritmo di ordinamento è superiore allo scambio eseguito. |
| 5. | È più efficiente dell'ordinamento di selezione. | È meno efficiente dell'ordinamento per inserzione. |
| 6. | Qui l'elemento è noto in anticipo e cerchiamo la posizione corretta in cui posizionarlo. | La posizione in cui posizionare l'elemento è nota in precedenza, cerchiamo l'elemento da inserire in quella posizione. |
| 7. | L'ordinamento per inserimento viene utilizzato quando:
| L'ordinamento della selezione viene utilizzato quando
|
| 8. | L'ordinamento per inserzione è Adattivo, cioè efficiente per insiemi di dati già sostanzialmente ordinati: la complessità temporale è O(kn) quando ogni elemento nell'input non è superiore a K posti lontani dalla sua posizione ordinata | L'ordinamento di selezione è un algoritmo di ordinamento per confronto sul posto |