logo

TechCodeview

Forskjellen mellom innsettingssortering og utvalgssortering

Innsettingssortering og utvalgssortering er to populære sorteringsalgoritmer, og hovedforskjellen deres ligger i hvordan de velger og plasserer elementer i en sortert sekvens.

Utvalgssortering:

  1. I utvalgssortering er inndatamatrisen delt inn i to deler: en sortert del og en usortert del.
  2. Algoritmen finner gjentatte ganger minimumselementet i den usorterte delen og bytter det med elementet lengst til venstre i den usorterte delen, og utvider dermed den sorterte delen med ett element.
  3. Utvalgssortering har en tidskompleksitet på O(n^2) i alle tilfeller.

Innsettingssortering:

  1. Ved innsettingssortering er inndatamatrisen også delt inn i to deler: en sortert del og en usortert del.
    Algoritmen plukker opp et element fra den usorterte delen og plasserer det i riktig posisjon i den sorterte delen, og flytter de større elementene en posisjon til høyre.
    Innsettingssortering har en tidskompleksitet på O(n^2) i verste fall, men kan yte bedre på delvis sorterte arrays, med en best-case tidskompleksitet på O(n).
    Hovedforskjeller:
  2. Utvalgssortering skanner den usorterte delen for å finne minimumselementet, mens innsettingssortering skanner den sorterte delen for å finne riktig posisjon for å plassere elementet.
    Utvalgssortering krever færre bytter enn innsettingssortering, men flere sammenligninger.
    Innsettingssortering er mer effektiv enn utvalgssortering når inndatamatrisen er delvis sortert eller nesten sortert, mens utvalgssortering gir bedre resultater når matrisen er svært usortert.
    Oppsummert har begge algoritmene en lignende tidskompleksitet, men deres valg og plasseringsmetoder er forskjellige. Valget mellom dem avhenger av egenskapene til inngangsdataene og de spesifikke kravene til problemet.

Fordeler med innsettingssortering:

  1. Enkel og lett å forstå og implementere.
  2. Effektiv for små datasett eller nesten sorterte data.
  3. In-place sorteringsalgoritme, noe som betyr at den ikke krever ekstra minne.
  4. Stabil sorteringsalgoritme, noe som betyr at den opprettholder den relative rekkefølgen av like elementer i inngangsmatrisen.

Ulemper med innsettingssortering:

  1. Ineffektiv for store datasett eller omvendt rekkefølgende data, med en verstefalls tidskompleksitet på O(n^2).
  2. Insertion sort har mange bytter, som kan gjøre det tregt på moderne datamaskiner.

Fordeler med utvalgssortering:

  1. Enkel og lett å forstå og implementere.
  2. Effektiv for små datasett eller nesten sorterte data.
  3. In-place sorteringsalgoritme, noe som betyr at den ikke krever ekstra minne.

Ulemper med utvalgssortering:

  1. Ineffektiv for store datasett, med en verste fall tidskompleksitet på O(n^2).
  2. Selection sort har mange sammenligninger, noe som kan gjøre det tregt på moderne datamaskiner.
  3. Ustabil sorteringsalgoritme, noe som betyr at den kanskje ikke opprettholder den relative rekkefølgen av like elementer i inngangsmatrisen.

I denne artikkelen vil vi diskutere forskjellen mellom innsettingssortering og utvalgssortering:



Innsettingssortering er en enkel sorteringsalgoritme som fungerer på samme måte som du sorterer spillekort i hendene. Matrisen er praktisk talt delt inn i en sortert og en usortert del. Verdier fra den usorterte delen plukkes og plasseres på riktig plass i den sorterte delen.

Algoritme:
Slik sorterer du en matrise med størrelse n i stigende rekkefølge:

  • Iterer fra arr[1] til arr[n] over matrisen.
  • Sammenlign gjeldende element (nøkkel) med forgjengeren.
  • Hvis nøkkelelementet er mindre enn forgjengeren, kan du sammenligne det med elementene før. Flytt de større elementene en posisjon opp for å gjøre plass til det byttet element.

Nedenfor er bildet for å illustrere innsettingssortering:



innsetting-sort

Nedenfor er programmet for det samme:

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]> tast) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nøkkel; } } // Funksjon for å skrive ut en matrise med størrelse N void printArray(int arr[], int n) { int i; // Skriv ut matrisen 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; }> 

>

>

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]> tast) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nøkkel; } } // Funksjon for å skrive ut en matrise med størrelse N static void printArray(int arr[], int n) { int i; // Skriv ut matrisen for (i = 0; i System.out.print(arr[i] + ' '); } System.out.println(); } // Driverkode offentlig statisk void main(String[ ] args) { int arr[] = { 12, 11, 13, 5, 6 }; int N = arr.length; Denne koden er bidratt av 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]>nøkkel):> >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]> tast) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nøkkel; } } // Funksjon for å skrive ut en matrise med størrelse N static void printArray(int[] arr, int n) { int i; // Skriv ut matrisen for (i = 0; i { Console.Write(arr[i] + ' '); } Console.WriteLine(); } // Driverkode statisk offentlig void Main() { int[] arr = new int[] { 12, 11, 13, 5, 6 }; int N = arr. Lengde; bidratt av 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]> tast) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nøkkel; } } // Funksjon for å skrive ut en matrise med størrelse N funksjon printArray(arr,n) { let i; // Skriv ut matrisen for (i = 0; i document.write(arr[i] + ' '); } document.write(' '); } // Driverkode la arr=[12, 11 , 13, 5, 6]; la N = arr.length; // Function Call insertionSort(arr, N); 

> 
    
 5 6 11 12 13>

De utvalg sortering algoritmen sorterer en matrise ved gjentatte ganger å finne minimumselementet (vurderer stigende rekkefølge) fra den usorterte delen og sette den i begynnelsen. Algoritmen opprettholder to undermatriser i en gitt matrise.

  • Undermatrisen er allerede sortert.
  • Den gjenværende undergruppen er usortert.

I hver iterasjon av utvalgssorteringen blir minimumselementet (med tanke på stigende rekkefølge) fra den usorterte undergruppen plukket og flyttet til den sorterte undergruppen.

Nedenfor er et eksempel for å forklare trinnene ovenfor:

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>

Nedenfor er programmet for det samme:

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> 

>

>

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#


java len av array



// 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> 

>

>

Produksjon: 

Sorted array: 11 12 22 25 64>

Tabellforskjell mellom innsettingssortering og utvalgssortering:

Innsettingssortering Utvalgssortering
1. Setter inn verdien i den forhåndssorterte matrisen for å sortere settet med verdier i matrisen. Finner minimum / maksimum antall fra listen og sorterer det i stigende / synkende rekkefølge.
2. Det er en stabil sorteringsalgoritme. Det er en ustabil sorteringsalgoritme.
3. Den beste tidskompleksiteten er Ω(N) når matrisen allerede er i stigende rekkefølge. Den har Θ(N2) i verste fall og gjennomsnittlig tilfelle. For beste tilfelle har worst case og gjennomsnittlig utvalgssort kompleksitet Θ(N2).
4. Antall sammenligningsoperasjoner utført i denne sorteringsalgoritmen er mindre enn byttet utført. Antall sammenligningsoperasjoner utført i denne sorteringsalgoritmen er flere enn byttet som utføres.
5. Det er mer effektivt enn utvalgssortering. Det er mindre effektivt enn innsettingssorten.
6. Her er elementet kjent på forhånd, og vi søker etter riktig posisjon for å plassere dem. Plasseringen hvor elementet skal plasseres er tidligere kjent, vi søker etter elementet som skal settes inn i den posisjonen.
7.

Innsettingssorteringen brukes når:

  • Matrisen har et lite antall elementer
  • Det er bare noen få elementer igjen som skal sorteres

Utvalget sortering brukes når

  • En liten liste skal sorteres
  • Kostnaden for å bytte spiller ingen rolle
  • Kontroll av alle elementene er obligatorisk
  • Kostnaden for å skrive til minnet er viktig som i flash-minne (antall swaps er O(n) sammenlignet med O(n2) av boblesorten)
8. Innsettingssorteringen er adaptiv, dvs. effektiv for datasett som allerede er vesentlig sortert: tidskompleksiteten er O(kn) når hvert element i inngangen ikke er mer enn k steder borte fra sin sorterte posisjon Utvalgssortering er en på stedet sammenligningssorteringsalgoritme