Insättningssortering: Algoritm med C, C++, Java, Python Exempel
Sarah Chen
Vad är insättningssortering?
Insättningssortering är en av jämförelsesorteringsalgoritmerna som används för att sortera element genom att iterera på ett element i taget och placera elementet i dess korrekta position.
Varje element infogas sekventiellt i en redan sorterad lista. Storleken på den redan sorterade listan är initialt en. Algoritmen för insättningssortering säkerställer att de första k elementen sorteras efter den k:te iterationen.
Egenskaper för insättningssorteringsalgoritm
Algoritmen för insättningssortering har följande viktiga egenskaper:
- Det är en stabil sorteringsteknik, så den ändrar inte den relativa ordningen för lika element.
- Det är effektivt för mindre datamängder men inte effektivt för större listor.
- Insättningssortering är adaptiv, vilket minskar det totala antalet steg om det är delvis sorterat. array tillhandahålls som input för att göra det effektivt.
Hur sätts in Operation arbete?
I Insertion Sort-algoritmen används infogningsoperationen för att sortera osorterade element. Det hjälper att infoga ett nytt element i en redan sorterad lista.
Pseudokod för infogningsoperation:
Betrakta en lista A med N element.
A[N-1] is the element to be inserted in the sorted sublist A[0..N-2]. For i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else Stop
I exemplet ovan ska ett nytt element 6 infogas i en redan sorterad lista.
Steg 1) Jämfört med det vänstra intilliggande elementet av A[5], 9 > 6, byter vi positionen för 9 och 6. Nu flyttas element 6 till A[4].
Steg 2) Nu jämför vi A[4] och A[3], och vi finner att A[3] > A[4], vi byter återigen positionen 6 och 8.
Steg 3) Jämför nu A[3] och A[2], eftersom A[2] > A[3] byter position 7 och 6.
Steg 4) Vi jämför A[1] och A[2], och som A[1] < A[2], dvs det vänstra intilliggande elementet är inte längre större. Nu drar vi slutsatsen att 6 är korrekt infogat och vi stoppar algoritmen här.
Hur insättningssorteringen fungerar
Insättningsoperationen som diskuterats ovan är ryggraden i infogningssorten. Infogningsproceduren exekveras på varje element, och i slutändan får vi den sorterade listan.
Exemplet ovan visar hur infogningssorteringen fungerar i datastrukturen. Inledningsvis finns bara ett element i den sorterade underlistan, dvs. 4. Efter att ha infogat A[1], dvs. 3, växer storleken på den sorterade underlistan till 2.
C++ Program för insättningssortering
#include <iostream>
using namespace std;
int main(){
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
cout << "\nUnsorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
int current_element,temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
cout << "\nSorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
return 0;
}
Produktion:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
C-kod för insättningssortering
#include <stdio.h>
int main() {
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
printf("\nUnsorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
int current_element, temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
printf("\nSorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
return 0;
}
Produktion:
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python Program för insättningssortering
#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]
#size of list
size_unsorted = len(unsorted)
#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
for i in range(1, size_unsorted):
current_element = unsorted[i]
j = i - 1
while j >= 0 and unsorted[j] > current_element:
#swapping if current element is lesser
unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
j -= 1
#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
Produktion:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Egenskaper för insättningssortering
Här är viktiga egenskaper för infogningssortering:
- Uppkopplad: Infogningssortering kan sortera element allt eftersom den tar emot. Det vill säga, om vi redan har sorterat en lista med element och lagt till några fler element i listorna, så behöver vi inte köra hela sorteringsproceduren igen. Istället behöver vi bara iterera på nyligen tillagda element.
- På plats: Utrymmeskomplexiteten för insättningssorteringsalgoritmen är konstant och kräver inte extra utrymme. Denna algoritm sorterar element på plats.
- Stabil: Vid insättningssortering byter vi inte elementen om deras värden är lika. Till exempel, två element, x och y, är lika, och x visas före y i osorterade listor, sedan i den sorterade listan kommer x att visas före y. Detta gör insättningssorteringen stabil.
- Anpassningsbar: A sorteringsalgoritm är adaptiv om det tar kortare tid om ingångselementen eller delmängden av element redan är sorterade. Som vi diskuterade ovan är den bästa körtiden för insättningssorteringen O(N), och den sämsta körtiden är O(N^2). Insättningssortering är en av de adaptiva sorteringsalgoritmerna.
Insättningssorteringens komplexitet
Rymdkomplexitet
Insättningssorteringen kräver inte extra utrymme för att sortera elementen, utrymmets komplexitet är konstant, dvs O(1).
Tidskomplexitet
Eftersom insättningssortering itererar varje element samtidigt, kräver det N-1 pass för att sortera N element. För varje pass kan den göra nollbyten om elementen redan är sorterade, eller byta om elementen är ordnade i fallande ordning.
- För pass 1 är de minsta erforderliga bytena noll och de maximala bytena som krävs är 1.
- För pass 2 är de minsta erforderliga bytena noll och de maximala bytena som krävs är 2.
- För pass N är det minsta swap som krävs noll, och det maximala swap som krävs är N.
- Minsta swap är noll, så den bästa tidskomplexiteten är O(N) för att iterera N pass.
- Totala maximala swappar är (1+2+3+4+..+N) i. N(N+1)/2, den värsta tidskomplexiteten är O(N^2).
Här är den viktiga tidskomplexiteten för infogningssortering:
- Worst Case Complexity: O(n2): Att sortera en array i fallande ordning när den är i stigande ordning är det värsta scenariot.
- Best Case-komplexitet: O(n): Best Case-komplexitet uppstår när arrayen redan är sorterad, den yttre slingan körs n antal gånger medan den inre slingan inte körs alls. Det finns bara ett antal jämförelser. Så i det här fallet är komplexiteten linjär.
- Genomsnittlig ärendekomplexitet: O(n2): Det händer när elementen i en array förekommer i den blandade ordningen, som varken är stigande eller fallande.
Sammanfattning
- Insättningssortering är en sorteringsalgoritmmetod som är baserad på jämförelsen.
- Det är en stabil sorteringsteknik, så den ändrar inte den relativa ordningen för lika element.
- På varje element används infogningsoperationen för att infoga elementet i den sorterade underlistan.
- Insättningssortering är en sorteringsalgoritm på plats.
- Den sämsta och genomsnittliga tidskomplexiteten för insättningssorteringen är kvadratisk, dvs O(N^2).
- Insättningssortering kräver inget extra utrymme.
