logo

TechCodeview

Diferència entre l'ordenació per inserció i l'ordenació per selecció

L'ordenació per inserció i l'ordenació per selecció són dos algorismes d'ordenació populars, i la seva principal diferència rau en com seleccionen i col·loquen els elements en una seqüència ordenada.

Ordenació de la selecció:

  1. En l'ordenació per selecció, la matriu d'entrada es divideix en dues parts: una part ordenada i una part no ordenada.
  2. L'algorisme troba repetidament l'element mínim a la part no ordenada i l'intercanvia amb l'element més a l'esquerra de la part no ordenada, ampliant així la part ordenada en un element.
  3. L'ordenació de selecció té una complexitat temporal de O(n^2) en tots els casos.

Ordenació d'inserció:

  1. En l'ordenació per inserció, la matriu d'entrada també es divideix en dues parts: una part ordenada i una part no ordenada.
    L'algorisme recull un element de la part no ordenada i el col·loca a la posició correcta a la part ordenada, desplaçant els elements més grans una posició cap a la dreta.
    L'ordenació d'inserció té una complexitat temporal de O(n^2) en el pitjor dels casos, però pot funcionar millor en matrius parcialment ordenades, amb una complexitat temporal en el millor dels casos de O(n).
    Principals diferències:
  2. L'ordenació per selecció escaneja la part no ordenada per trobar l'element mínim, mentre que l'ordenació per inserció explora la part ordenada per trobar la posició correcta per col·locar l'element.
    L'ordenació per selecció requereix menys intercanvis que l'ordenació per inserció, però més comparacions.
    L'ordenació per inserció és més eficient que l'ordenació per selecció quan la matriu d'entrada està ordenada parcialment o gairebé ordenada, mentre que l'ordenació per selecció funciona millor quan la matriu no està molt ordenada.
    En resum, ambdós algorismes tenen una complexitat temporal similar, però els seus mètodes de selecció i col·locació difereixen. L'elecció entre elles depèn de les característiques de les dades d'entrada i dels requisits específics del problema en qüestió.

Avantatges de l'ordenació d'inserció:

  1. Simple i fàcil d'entendre i implementar.
  2. Eficaç per a conjunts de dades petits o dades gairebé ordenades.
  3. Algorisme d'ordenació in situ, és a dir, no requereix memòria addicional.
  4. Algorisme d'ordenació estable, el que significa que manté l'ordre relatiu dels elements iguals a la matriu d'entrada.

Desavantatges de l'ordenació d'inserció:

  1. Ineficient per a grans conjunts de dades o dades d'ordre invers, amb una complexitat temporal en el pitjor dels casos de O(n^2).
  2. L'ordenació d'inserció té molts intercanvis, cosa que pot fer que sigui lent als ordinadors moderns.

Avantatges de l'ordenació de selecció:

  1. Simple i fàcil d'entendre i implementar.
  2. Eficaç per a conjunts de dades petits o dades gairebé ordenades.
  3. Algorisme d'ordenació in situ, és a dir, no requereix memòria addicional.

Desavantatges de l'ordenació de selecció:

  1. Ineficient per a grans conjunts de dades, amb una complexitat temporal en el pitjor dels casos de O (n ^ 2).
  2. L'ordenació de selecció té moltes comparacions, cosa que pot fer que sigui lent als ordinadors moderns.
  3. Algorisme d'ordenació inestable, el que significa que pot no mantenir l'ordre relatiu d'elements iguals a la matriu d'entrada.

En aquest article, parlarem de la diferència entre l'ordenació d'inserció i l'ordenació de selecció:



Classificació per inserció és un algorisme d'ordenació senzill que funciona de manera semblant a la manera d'ordenar les cartes a les mans. La matriu es divideix pràcticament en una part ordenada i una part no ordenada. Els valors de la part no ordenada es trien i es col·loquen a la posició correcta de la part ordenada.

Algorisme:
Per ordenar una matriu de mida n en ordre ascendent:

  • Itera des de arr[1] fins a arr[n] per la matriu.
  • Compareu l'element actual (clau) amb el seu predecessor.
  • Si l'element clau és més petit que el seu predecessor, compareu-lo amb els elements anteriors. Mou els elements més grans una posició cap amunt per fer espai per a l'element intercanviat.

A continuació es mostra la imatge per il·lustrar l'ordenació d'inserció:



inserció-ordenació

A continuació es mostra el programa del mateix:

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]> tecla) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = clau; } } // Funció per imprimir una matriu de mida N void printArray(int arr[], int n) { int i; // Imprimeix la matriu per a (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; }> 

>

>

Java




// 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]> tecla) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = clau; } } // Funció per imprimir una matriu de mida N static void printArray(int arr[], int n) { int i; // Imprimeix la matriu per a (i = 0; i System.out.print(arr[i] + ' '); } System.out.println(); } // Codi del controlador public static void main(String[ ] args) { int arr[] = { 12, 11, 13, 5, 6 } int N = arr.length // Inserció de la funció (arr, N) //; Aquest codi és aportat per code_hunt>> 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  # 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]>clau):> >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]> tecla) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = clau;  } } // Funció per imprimir una matriu de mida N static void printArray(int[] arr, int n) { int i;  // Imprimeix la matriu per a (i = 0; i { Console.Write(arr[i] + ' '); } Console.WriteLine(); } // Codi del controlador static public void Main() { int[] arr = new int[] { 12, 11, 13, 5, 6 } int N = arr.Longitud // Inserció de la funció (arr, N } } // Aquest codi és aportat per Dharanendra L V>>> 
  
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  > // 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]> tecla) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = clau;  } } // Funció per imprimir una matriu de mida N function printArray(arr,n) { let i;    // Imprimeix la matriu per a (i = 0; i document.write(arr[i] + ' '); } document.write(' '); } // Codi del controlador let arr=[12, 11 , 13, 5, 6]; let N = arr.length // Inserció de la funció (arr, N) // Aquest codi és aportat per avanitrachhadiya2155; 
  
 
    
 
> 
    
 5 6 11 12 13>
 
El ordenació de selecció L'algoritme ordena una matriu trobant repetidament l'element mínim (tenint en compte l'ordre ascendent) de la part no ordenada i posant-lo al principi. L'algorisme manté dos subarrays en una matriu donada.
 
     
  • El subbarrat ja està ordenat.
    •  
  • El subbarray restant no està ordenat.
    •  
 
En cada iteració de l'ordenació de selecció, l'element mínim (considerant l'ordre ascendent) de la subbarra no ordenada s'escull i es mou a la subbarra ordenada.
 
A continuació es mostra un exemple per explicar els passos anteriors:
 
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>
 
A continuació es mostra el programa del mateix:
 
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; }> 
  
 
    
 
>
 
    
 
>
 
 
Java
    
 
     
  
 
    
 
     
     
    
 
 
  
  // 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> 
  
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
  
  # 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#
    
 
     
  
java ordenant una llista

 
    
 
     
     
    
 
 
  
  // 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> 
  
 
    
 
>
 
    
 
>
 
  Sortida:  
 
Sorted array: 11 12 22 25 64>
 
  Diferència tabular entre l'ordenació per inserció i l'ordenació per selecció:  
 
 
   Ordenació d'inserció Ordenació de la selecció 
  
 1. Insereix el valor a la matriu preordenada per ordenar el conjunt de valors de la matriu. Troba el nombre mínim / màxim de la llista i l'ordena en ordre ascendent / descendent. 
 
 2. És un algorisme d'ordenació estable. És un algorisme d'ordenació inestable. 
 
 3. La complexitat temporal en el millor dels casos és Ω(N) quan la matriu ja està en ordre ascendent. Té Θ(N2) en el pitjor dels casos i en els casos mitjans. En el millor dels casos, el pitjor dels casos i la selecció mitjana tenen complexitat Θ(N2). 
 
 4. El nombre d'operacions de comparació realitzades en aquest algorisme d'ordenació és menor que l'intercanvi realitzat. El nombre d'operacions de comparació realitzades en aquest algorisme d'ordenació és superior a l'intercanvi realitzat. 
 
 5. És més eficient que l'ordenació Selecció. És menys eficient que l'ordenació d'inserció. 
 
 6. Aquí es coneix prèviament l'element, i busquem la posició correcta per col·locar-los. La ubicació on posar l'element es coneix prèviament busquem l'element per inserir en aquesta posició. 
 
   7.    
L'ordenació d'inserció s'utilitza quan:
 
     
  • La matriu té un nombre reduït d'elements
    •  
  • Només queden pocs elements per ordenar
    •  
 		  
L'ordenació de selecció s'utilitza quan
 
     
  • S'ha d'ordenar una petita llista
    •  
  • El cost del canvi no importa
    •  
  • La comprovació de tots els elements és obligatòria
    •  
  • El cost d'escriure a la memòria és important com a la memòria flash (el nombre d'intercanvis és O (n) en comparació amb O (n2) de l'ordenació de bombolles)
    •  
 		 
 
   8.   L'ordenació d'inserció és adaptativa, és a dir, eficient per a conjunts de dades que ja estan substancialment ordenats: la complexitat del temps és O (kn) quan cada element de l'entrada no és més que k llocs lluny de la seva posició ordenada L'ordenació per selecció és un algorisme d'ordenació de comparació in situ