Sorteringsalgoritme

I denne vejledning lærer du, hvordan indsætningssortering fungerer. Du finder også arbejdseksempler på indsættelsessortering i C, C ++, Java og Python.

Indsats sortering fungerer på samme måde, som vi sorterer kort i vores hånd i et kortspil.

Vi antager, at det første kort allerede er sorteret, vælger vi et usorteret kort. Hvis det usorterede kort er større end kortet i hånden, placeres det til højre ellers til venstre. På samme måde tages andre usorterede kort og placeres på deres rette sted.

En lignende fremgangsmåde bruges ved indsættelsessortering.

Indsorteringssortering er en sorteringsalgoritme, der placerer et usorteret element på sit passende sted i hver iteration.

Hvordan indsættelsessortering fungerer?

Antag, at vi skal sortere følgende array.

Indledende array
  1. Det første element i arrayet antages at være sorteret. Tag det andet element, og opbevar det separat i key.
    Sammenlign keymed det første element. Hvis det første element er større end key, placeres nøglen foran det første element. Hvis det første element er større end nøglen, placeres nøglen foran det første element.
  2. Nu er de to første elementer sorteret.
    Tag det tredje element og sammenlign det med elementerne til venstre for det. Placerede det lige bag elementet mindre end det. Hvis der ikke er noget mindre end det, skal du placere det i begyndelsen af ​​arrayet. Placer 1 i starten
  3. På samme måde skal du placere hvert usorteret element på sin korrekte position. Placer 4 bag 1 Placer 3 bag 1, og arrayet sorteres

Sorteringsalgoritme

 insertionSort (matrix) markerer det første element som sorteret for hvert usorterede element X 'udtrækker' elementet X for j X flyt det sorterede element til højre med 1 break-løkke og indsæt X her slut indsættelseSort

Python, Java og C / C ++ eksempler

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); )

Kompleksitet

Tidskompleksiteter

  • Kompleksitet i værste tilfælde: Antag, en matrix er i stigende rækkefølge, og du vil sortere den i faldende rækkefølge. I dette tilfælde opstår kompleksitet i værste tilfælde. Hvert element skal sammenlignes med hvert af de andre elementer, så for hvert nte element foretages antallet af sammenligninger. Således er det samlede antal sammenligninger =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Best case-kompleksitet: O(n)
    Når arrayet allerede er sorteret, kører den ydre loop nflere gange, mens den indre loop slet ikke kører. Så der er kun nantal sammenligninger. Således er kompleksitet lineær.
  • Gennemsnitlig sagskompleksitet: Det sker, når elementerne i en matrix er i sammenblandet rækkefølge (hverken stigende eller faldende).O(n2)

Rumkompleksitet

Rumkompleksitet O(1)skyldes, at der bruges en ekstra variabel key.

Indsætningssorteringsapplikationer

Indsættelsessorteringen bruges, når:

  • arrayet har et lille antal elementer
  • der er kun få elementer tilbage, der skal sorteres

Interessante artikler...