Invoegsorteeralgoritme

In deze tutorial leert u hoe invoegsortering werkt. Ook vindt u werkende voorbeelden van invoegsortering in C, C ++, Java en Python.

Invoegsortering werkt op dezelfde manier als we kaarten in onze hand sorteren in een kaartspel.

We gaan ervan uit dat de eerste kaart al gesorteerd is, we selecteren een ongesorteerde kaart. Als de ongesorteerde kaart groter is dan de kaart in de hand, wordt deze aan de rechterkant geplaatst, anders aan de linkerkant. Op dezelfde manier worden andere ongesorteerde kaarten genomen en op hun juiste plaats gelegd.

Een vergelijkbare benadering wordt gebruikt door invoegsortering.

Invoegsortering is een sorteeralgoritme dat een ongesorteerd element op de juiste plaats in elke iteratie plaatst.

Hoe werkt invoegsortering?

Stel dat we de volgende array moeten sorteren.

Eerste array

1. Aangenomen wordt dat het eerste element in de array is gesorteerd. Pak het tweede element en berg dit apart op key.
   Vergelijk keymet het eerste element. Als het eerste element groter is dan key, wordt de sleutel voor het eerste element geplaatst. Als het eerste element groter is dan de sleutel, wordt de sleutel voor het eerste element geplaatst.
2. Nu zijn de eerste twee elementen gesorteerd.
   Neem het derde element en vergelijk het met de elementen aan de linkerkant ervan. Geplaatst net achter het element kleiner dan het. Als er geen element kleiner is, plaats het dan aan het begin van de array. Plaats 1 aan het begin
3. Plaats op dezelfde manier elk ongesorteerd element op de juiste positie. Plaats 4 achter 1 Plaats 3 achter 1 en de array is gesorteerd

Invoegsorteeralgoritme

 insertionSort (array) markeer het eerste element als gesorteerd voor elk ongesorteerd element X 'extraheer' het element X voor j X verplaats het gesorteerde element naar rechts met 1 break-loop en voeg hier X in end insertionSort

Python, Java en C / C ++ voorbeelden

Python Java C C ++

 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)

  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )

 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Complexiteit

Tijdscomplexiteit

• Complexiteit in het ergste geval: stel dat een array in oplopende volgorde staat en u deze in aflopende volgorde wilt sorteren. In dit geval treedt de complexiteit in het ergste geval op. Elk element moet worden vergeleken met elk van de andere elementen, dus voor elk n-de element wordt een aantal vergelijkingen gemaakt. Het totale aantal vergelijkingen =O(n2)

(n-1)
n*(n-1) ~ n2
• Complexiteit in het beste geval: O(n)
  wanneer de array al is gesorteerd, wordt de buitenste lus een naantal keren uitgevoerd, terwijl de binnenste lus helemaal niet wordt uitgevoerd. Er zijn dus slechts een naantal vergelijkingen. De complexiteit is dus lineair.
• Gemiddelde hoofdlettercomplexiteit: het treedt op wanneer de elementen van een array in een door elkaar gegooide volgorde staan ​​(noch oplopend noch aflopend).O(n2)

Complexiteit van de ruimte

Ruimtecomplexiteit komt O(1)doordat er een extra variabele keywordt gebruikt.

Invoegsorteringstoepassingen

De invoegsortering wordt gebruikt wanneer:

• de array heeft een klein aantal elementen
• er zijn nog maar een paar elementen die moeten worden gesorteerd