Insättningssortering och urvalssortering är två populära sorteringsalgoritmer, och deras huvudsakliga skillnad ligger i hur de väljer och placerar element i en sorterad sekvens.
Urvalssortering:
- I urvalssortering är inmatningsmatrisen uppdelad i två delar: en sorterad del och en osorterad del.
- Algoritmen hittar upprepade gånger minimielementet i den osorterade delen och byter ut det med elementet längst till vänster i den osorterade delen, och expanderar på så sätt den sorterade delen med ett element.
- Urvalssortering har en tidskomplexitet på O(n^2) i alla fall.
Insättningssortering:
- Vid insättningssortering är inmatningsmatrisen också uppdelad i två delar: en sorterad del och en osorterad del.
Algoritmen plockar upp ett element från den osorterade delen och placerar det i rätt position i den sorterade delen, och flyttar de större elementen en position åt höger.
Insättningssortering har en tidskomplexitet på O(n^2) i värsta fall, men kan prestera bättre på partiellt sorterade arrayer, med en tidskomplexitet för bästa fallet på O(n).
Huvudsakliga skillnader: - Selection sort skannar den osorterade delen för att hitta minimielementet, medan insättningssorteringen skannar den sorterade delen för att hitta rätt position för att placera elementet.
Urvalssortering kräver färre byten än infogningssortering, men fler jämförelser.
Insättningssortering är effektivare än urvalssortering när inmatningsmatrisen är delvis sorterad eller nästan sorterad, medan urvalssortering fungerar bättre när matrisen är mycket osorterad.
Sammanfattningsvis har båda algoritmerna en liknande tidskomplexitet, men deras urval och placeringsmetoder skiljer sig åt. Valet mellan dem beror på egenskaperna hos indata och de specifika kraven för det aktuella problemet.
Fördelar med insättningssortering:
- Enkelt och lätt att förstå och implementera.
- Effektiv för små datamängder eller nästan sorterade data.
- In-place sorteringsalgoritm, vilket innebär att den inte kräver extra minne.
- Stabil sorteringsalgoritm, vilket betyder att den upprätthåller den relativa ordningen av lika element i inmatningsmatrisen.
Nackdelar med insättningssortering:
- Ineffektiv för stora datamängder eller data i omvänd ordning, med en tidskomplexitet i värsta fall på O(n^2).
- Insättningssort har många byten, vilket kan göra det långsamt på moderna datorer.
Fördelar med urvalssortering:
- Enkelt och lätt att förstå och implementera.
- Effektiv för små datamängder eller nästan sorterade data.
- In-place sorteringsalgoritm, vilket innebär att den inte kräver extra minne.
Nackdelar med urvalssortering:
- Ineffektiv för stora datamängder, med en tidskomplexitet i värsta fall på O(n^2).
- Selection sort har många jämförelser, vilket kan göra det långsamt på moderna datorer.
- Instabil sorteringsalgoritm, vilket betyder att den kanske inte upprätthåller den relativa ordningen av lika element i inmatningsmatrisen.
I den här artikeln kommer vi att diskutera skillnaden mellan infogningssorteringen och urvalssorteringen:
Insättningssort är en enkel sorteringsalgoritm som fungerar på samma sätt som du sorterar spelkort i dina händer. Arrayen är praktiskt taget uppdelad i en sorterad och en osorterad del. Värden från den osorterade delen plockas och placeras på rätt plats i den sorterade delen.
Algoritm:
Så här sorterar du en matris med storlek n i stigande ordning:
- Iterera från arr[1] till arr[n] över arrayen.
- Jämför det nuvarande elementet (nyckeln) med dess föregångare.
- Om nyckelelementet är mindre än dess föregångare, jämför det med elementen tidigare. Flytta de större elementen en position upp för att göra plats för det utbytta elementet.
Nedan är bilden för att illustrera insättningssorteringen:
Nedan är programmet för detsamma:
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]> nyckel) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nyckel; } } // Funktion för att skriva ut en array med storleken N void printArray(int arr[], int n) { int i; // Skriv ut arrayen för (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]> nyckel) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nyckel; } } // Funktion för att skriva ut en array av storlek N static void printArray(int arr[], int n) { int i; // Skriv ut arrayen för (i = 0; i System.out.print(arr[i] + ' '); } System.out.println(); } // Driver code public static void main(String[ ] args) { int arr[] = { 12, 11, 13, 5, 6 }; int N = arr.length; Denna kod bidrar med 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]>nyckel):> >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]> nyckel) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nyckel; } } // Funktion för att skriva ut en array av storlek N static void printArray(int[] arr, int n) { int i; // Skriv ut arrayen för (i = 0; i { Console.Write(arr[i] + ' '); } Console.WriteLine(); } // Driver code static public void Main() { int[] arr = new int[] { 12, 11, 13, 5, 6 }; int N = arr.Length; bidragit 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]> nyckel) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = nyckel; } } // Funktion för att skriva ut en array med storlek N funktion printArray(arr,n) { let i; // Skriv ut arrayen för (i = 0; i document.write(arr[i] + ' '); } document.write(' '); } // Driver code let arr=[12, 11 , 13, 5, 6]; låt N = arr.length; // Funktion Call insertionSort(arr, N); |
>5 6 11 12 13>
De urval sortera algoritmen sorterar en array genom att upprepade gånger hitta minimielementet (med tanke på stigande ordning) från den osorterade delen och sätta den i början. Algoritmen upprätthåller två subarrayer i en given array.
- Undermatrisen är redan sorterad.
- Den återstående undermatrisen är osorterad.
I varje iteration av urvalssorteringen plockas minimielementet (med tanke på stigande ordning) från den osorterade subarrayen och flyttas till den sorterade subarrayen.
Nedan är ett exempel för att förklara stegen ovan:
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>
Nedan är programmet för detsamma:
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#
np.klipp
// 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> |
>
>Produktion:
Sorted array: 11 12 22 25 64>
Skillnad i tabellform mellan infogningssortering och urvalssortering:
| Insättningssortering | Urval Sortera | |
|---|---|---|
| 1. | Infogar värdet i den försorterade matrisen för att sortera uppsättningen värden i matrisen. | Hittar det lägsta/högsta antalet från listan och sorterar det i stigande/fallande ordning. |
| 2. | Det är en stabil sorteringsalgoritm. | Det är en instabil sorteringsalgoritm. |
| 3. | Den bästa tidskomplexiteten är Ω(N) när matrisen redan är i stigande ordning. Den har Θ(N2) i värsta fall och genomsnittligt fall. | För bästa fall har värsta fall och genomsnittlig urvalssort komplexitet Θ(N2). |
| 4. | Antalet jämförelseoperationer som utförs i denna sorteringsalgoritm är mindre än utbytet som utförs. | Antalet jämförelseoperationer som utförs i denna sorteringsalgoritm är fler än utbytet. |
| 5. | Det är mer effektivt än urvalssorteringen. | Det är mindre effektivt än Insertion sorten. |
| 6. | Här är elementet känt i förväg, och vi söker efter rätt position för att placera dem. | Platsen där elementet ska placeras är tidigare känt. Vi söker efter elementet att infoga på den positionen. |
| 7. | Insättningssorteringen används när:
| Urvalssorteringen används när
|
| 8. | Infogningssorteringen är adaptiv, d.v.s. effektiv för datamängder som redan är väsentligt sorterade: tidskomplexiteten är O(kn) när varje element i ingången inte är mer än k platser bort från dess sorterade position | Urvalssortering är en algoritm för jämförelsesortering på plats |