Sorteringsalgoritm

I denna handledning lär du dig hur insättningssortering fungerar. Du hittar också arbetsexempel på insättningssortering i C, C ++, Java och Python.

Insättningssortering fungerar på samma sätt som vi sorterar kort i handen i ett kortspel.

Vi antar att det första kortet redan är sorterat då, vi väljer ett osorterat kort. Om det osorterade kortet är större än kortet i handen placeras det till höger annars till vänster. På samma sätt tas andra osorterade kort och placeras på rätt plats.

Ett liknande tillvägagångssätt används av insättningssortering.

Insättningssortering är en sorteringsalgoritm som placerar ett osorterat element på sin lämpliga plats i varje iteration.

Hur fungerar insättningssortering?

Antag att vi måste sortera följande array.

Initial array
  1. Det första elementet i matrisen antas sorteras. Ta det andra elementet och förvara det separat i key.
    Jämför keymed det första elementet. Om det första elementet är större än key, placeras nyckeln framför det första elementet. Om det första elementet är större än tangenten, placeras nyckeln framför det första elementet.
  2. Nu är de två första elementen sorterade.
    Ta det tredje elementet och jämför det med elementen till vänster om det. Placerade den precis bakom elementet mindre än det. Om det inte finns något mindre än det, placera det i början av matrisen. Placera 1 i början
  3. Placera också alla osorterade element på rätt plats. Plats 4 bakom 1 Plats 3 bakom 1 och matrisen sorteras

Sorteringsalgoritm

 insertionSort (array) markera det första elementet som sorterat för varje osorterat element X 'extrahera' elementet X för j X flytta det sorterade elementet till höger med en brytslinga och infoga X här slutet insertionSort

Python, Java och C / C ++ exempel

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

Komplexitet

Tidskomplexiteter

  • Värstfallskomplexitet: Antag att en matris är i stigande ordning och du vill sortera den i fallande ordning. I detta fall inträffar komplexitet i värsta fall. Varje element måste jämföras med var och en av de andra elementen, så för varje nionde element görs antalet jämförelser. Således är det totala antalet jämförelser =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Bästa fallkomplexitet: O(n)
    När matrisen redan är sorterad körs den yttre slingan nflera gånger medan den inre slingan inte körs alls. Så det finns bara ett nantal jämförelser. Således är komplexitet linjär.
  • Genomsnittlig fallkomplexitet: Det inträffar när elementen i en matris är i rörlig ordning (varken stigande eller fallande).O(n2)

Rymdkomplexitet

Rymdkomplexitet O(1)beror på att en extra variabel keyanvänds.

Program för insättningssortering

Insättningssorteringen används när:

  • arrayen har ett litet antal element
  • det finns bara ett fåtal element kvar att sortera

Intressanta artiklar...