Denk aan de volgende cijfers:
50 60 30 10 80 70 20 40
Als deze lijst in oplopende volgorde wordt gesorteerd, zou dit zijn:
10 20 30 40 50 60 70 80
Als het in aflopende volgorde wordt gesorteerd, zou het zijn:
80 70 60 50 40 30 20 10
Invoegsortering is een sorteeralgoritme dat wordt gebruikt om de lijst in oplopende of aflopende volgorde te sorteren. In dit artikel wordt alleen in oplopende volgorde gesorteerd. Sorteren in aflopende volgorde volgt dezelfde logica als in dit document. Het doel van dit artikel is om de invoegsoort uit te leggen. Het programmeren gebeurt in het volgende voorbeeld in C. De invoegsortering wordt hier uitgelegd aan de hand van één array.
Algoritme voor invoegsortering
Er wordt een ongesorteerde lijst gegeven. Het doel is om de lijst in oplopende volgorde te sorteren met dezelfde lijst. Het sorteren van een ongesorteerde array met dezelfde array wordt ter plaatse sorteren genoemd. De op nul gebaseerde indexering wordt hier gebruikt. De stappen zijn als volgt:
-
- De lijst wordt vanaf het begin gescand.
- Terwijl het scannen aan de gang is, wordt elk aantal minder dan zijn voorganger verwisseld met zijn voorganger.
- Dit ruilen gaat door langs de lijst, totdat het niet meer mogelijk is om te ruilen.
- Wanneer het scannen het einde bereikt, is het sorteren voltooid.
Afbeelding invoegen Sorteren
Bij het omgaan met tijdcomplexiteit wordt normaal gesproken rekening gehouden met het slechtste geval. De slechtste regeling voor de vorige lijst is:
80 70 60 50 40 30 20 10
Er zijn acht elementen met indexen van nul tot 7.
Bij index nul gaat het scannen naar 80. Dit is één beweging. Deze ene beweging is een operatie. Er is tot nu toe in totaal één operatie geweest (één beweging, geen vergelijking en geen ruil). Het resultaat is:
| 80 70 60 50 40 30 20 10
Bij index één is er een beweging naar 70. 70 wordt vergeleken met 80. 70 en 80 worden verwisseld. Eén beweging is één operatie. Eén vergelijking is ook één operatie. Een swap is ook een operatie. Dit gedeelte biedt drie bewerkingen. Er zijn tot nu toe in totaal vier bewerkingen (1 + 3 = 4). Het resultaat is als volgt:
70 | 80 60 50 40 30 20 10
Bij index twee is er een beweging naar 60. 60 wordt vergeleken met 80, dan worden 60 en 80 verwisseld. 60 wordt vergeleken met 70, dan worden 60 en 70 verwisseld. Eén beweging is één operatie. Twee vergelijkingen zijn twee operaties. Twee swaps zijn twee operaties. Dit gedeelte biedt vijf bewerkingen. Er zijn tot nu toe in totaal negen operaties (4 + 5 = 9). Het resultaat is als volgt:
60 70 | 80 50 40 30 20 10
Bij index drie is er een beweging naar 50. 50 wordt vergeleken met 80, dan worden 50 en 80 verwisseld. 50 wordt vergeleken met 70, dan worden 50 en 70 verwisseld. 50 wordt vergeleken met 60, dan worden 50 en 60 verwisseld. Eén beweging is één operatie. Drie vergelijkingen zijn drie operaties. Drie swaps zijn drie operaties. Dit gedeelte biedt zeven bewerkingen. In totaal zijn er tot nu toe zestien operaties (9 + 7 = 16). Het resultaat is als volgt:
50 60 70 | 80 40 30 20 10
Bij index vier is er een beweging naar 40. 40 wordt vergeleken met 80, dan worden 40 en 80 verwisseld. 40 wordt vergeleken met 70, dan worden 40 en 70 verwisseld. 40 wordt vergeleken met 60, dan worden 40 en 60 verwisseld. 40 wordt vergeleken met 50, dan worden 40 en 50 verwisseld. Eén beweging is één operatie. Vier vergelijkingen zijn vier operaties. Vier swaps zijn vier operaties. Dit gedeelte biedt negen bewerkingen. Er zijn tot nu toe in totaal vijfentwintig operaties (16 + 9 = 25). Het resultaat is als volgt:
40 50 60 70 80 | 30 20 10
Bij index vijf is er een beweging naar 30. 30 wordt vergeleken met 80, dan worden 30 en 80 verwisseld. 30 wordt vergeleken met 70, dan worden 30 en 70 verwisseld. 30 wordt vergeleken met 60, dan worden 30 en 60 verwisseld. 30 wordt vergeleken met 50, dan worden 30 en 50 verwisseld. 30 wordt vergeleken met 40, dan worden 30 en 40 verwisseld. Eén beweging is één operatie. Vijf vergelijkingen zijn vijf operaties. Vijf swaps zijn vijf operaties. Dit gedeelte biedt elf bewerkingen. Er zijn tot nu toe in totaal 36 operaties (25 + 11 = 36). Het resultaat is als volgt:
30 40 50 60 70 80 | 20 10
Bij index zes is er een beweging naar 20. 20 wordt vergeleken met 80, dan worden 20 en 80 verwisseld. 20 wordt vergeleken met 70, dan worden 20 en 70 verwisseld. 20 wordt vergeleken met 60, dan worden 20 en 60 verwisseld. 20 wordt vergeleken met 50, dan worden 20 en 50 verwisseld. 20 wordt vergeleken met 40, dan worden 20 en 40 verwisseld. 20 wordt vergeleken met 30, dan worden 20 en 30 verwisseld. Eén beweging is één operatie. Zes vergelijkingen zijn zes operaties. Zes swaps zijn zes operaties. Dit gedeelte biedt dertien bewerkingen. Er zijn tot nu toe in totaal negenenveertig operaties (36 + 13 = 49). Het resultaat is als volgt:
20 30 40 50 60 70 80 | 10
Bij index zeven is er een beweging naar 10. 10 wordt vergeleken met 80, dan worden 10 en 80 verwisseld. 10 wordt vergeleken met 70, dan worden 10 en 70 verwisseld. 10 wordt vergeleken met 60, dan worden 10 en 60 verwisseld. 10 wordt vergeleken met 50, dan worden 10 en 50 verwisseld. 10 wordt vergeleken met 30, dan worden 10 en 40 verwisseld. 10 wordt vergeleken met 30, dan worden 10 en 30 verwisseld. 10 wordt vergeleken met 20, dan worden 10 en 20 verwisseld. Eén beweging is één operatie. Zeven vergelijkingen zijn zeven operaties. Zeven swaps zijn zeven operaties. Dit gedeelte biedt vijftien bewerkingen. In totaal zijn er tot nu toe vierenzestig operaties (49 + 15 = 64). Het resultaat is als volgt:
10 20 30 40 50 60 70 80 10 |
De klus is geklaard! 64 operaties waren betrokken.
64 = 8 x 8 = 8 twee
Tijdcomplexiteit voor invoegsortering
Als er n elementen zijn om te sorteren met Insertion Sort, zou het maximale aantal mogelijke bewerkingen n2 zijn, zoals eerder aangetoond. De complexiteit van de invoegsorteertijd is:
Op twee )
Hiervoor wordt de Big-O-notatie gebruikt. De Big-O-notatie begint met O in hoofdletters, gevolgd door haakjes. Tussen haakjes staat de uitdrukking voor het maximaal mogelijke aantal bewerkingen.
Coderen in C
Helemaal aan het begin van de scan kan het eerste element zijn positie niet veranderen. Het programma is in wezen het volgende:
#includeongeldige invoegingSorteren ( int A [ ] , int N ) {
voor ( int i = 0 ; i < N; ik++ ) {
intj = ik;
terwijl ( EEN [ j ] < EEN [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; EEN [ j ] = A [ j- 1 ] ; EEN [ j- 1 ] = temperatuur; // ruil
j--;
}
}
}
De functiedefinitie insertionSort() gebruikt het algoritme zoals beschreven. Let op de voorwaarden voor de while-loop. Een geschikte C-hoofdfunctie voor dit programma is:
{
int n = 8 ;
int A [ ] = { vijftig , 60 , 30 , 10 , 80 , 70 , twintig , 40 } ;
invoegingSorteren ( Een ) ;
voor ( int i = 0 ; i < n; ik++ ) {
printf ( '%i ' , EEN [ i ] ) ;
}
printf ( ' \n ' ) ;
opbrengst 0 ;
}
Conclusie
De tijdscomplexiteit voor Insertion Sort wordt gegeven als:
Op twee )
De lezer heeft misschien gehoord van een worst-case tijdcomplexiteit, gemiddelde-case tijdcomplexiteit en best-case tijdcomplexiteit. Deze variaties van de Insertion Sort Time Complexity worden besproken in het volgende artikel op onze website.