Lisamise sortimise algoritm

Selles õpetuses saate teada, kuidas sisestamise sortimine töötab. Samuti leiate toimivad näited sisestamise sortimisest C, C ++, Java ja Python.

Lisamise sortimine toimib sarnaselt kaardimängus meie käes olevate kaartide sorteerimisega.

Eeldame, et esimene kaart on siis juba sorteeritud, valime sortimata kaardi. Kui sortimata kaart on suurem kui käes olev kaart, asetatakse see muidu paremale, vasakule. Samamoodi võetakse ka teised sorteerimata kaardid ja pannakse neile õigesse kohta.

Sarnast lähenemist kasutatakse sisestamise sorteerimise korral.

Sisestussorteerimine on sorteerimisalgoritm, mis paigutab sorteerimata elemendi igas iteratsioonis sobivasse kohta.

Kuidas sisestamise sortimine töötab?

Oletame, et peame sorteerima järgmise massiivi.

Esialgne massiiv
  1. Eeldatakse, et massiivi esimene element on sorteeritud. Võtke teine ​​element ja hoidke seda eraldi key.
    Võrdle keyesimese elemendiga. Kui esimene element on suurem kui key, siis asetatakse võti esimese elemendi ette. Kui esimene element on võtmest suurem, asetatakse võti esimese elemendi ette.
  2. Nüüd on kaks esimest elementi sorteeritud.
    Võtke kolmas element ja võrrelge seda vasakul olevate elementidega. Paigutas selle just temast väiksema elemendi taha. Kui sellest pole ühtegi väiksemat elementi, asetage see massiivi algusesse. Pange 1 alguses
  3. Samamoodi asetage kõik sorteerimata elemendid õigesse asendisse. Asetage 4 taha 1 Asetage 3 1 taha ja massiiv on sorteeritud

Lisamise algoritm

 insertionSort (massiiv) märkige esimene element sorteerimata iga sorteerimata elemendi jaoks X 'ekstraktige' element X for j X liigutab sorteeritud elementi 1 katkestussilmu võrra paremale ja sisestage X siia lisamise lõpp

Pythoni, Java ja C / C ++ näited

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

Keerukus

Aja keerukus

  • Halvima juhtumi keerukus: Oletame, et massiiv on kasvavas järjekorras ja soovite sortida kahanevas järjekorras. Sel juhul tekib halvim juhtum. Kõiki elemente tuleb võrrelda teiste elementidega, nii et iga n-nda elemendi kohta tehakse mitu võrdlust. Seega on võrdluste koguarv =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Parima juhtumi keerukus: O(n)
    kui massiiv on juba sorteeritud, töötab välimine silmus nmitu korda, samas kui sisemine silmus ei tööta üldse. Niisiis, on ainult npalju võrdlusi. Seega on keerukus lineaarne.
  • Keskmine juhtumi keerukus: see juhtub siis, kui massiivi elemendid on segamini (ei tõusvas ega kahanevas).O(n2)

Ruumi keerukus

Ruumi keerukus tuleneb O(1)sellest, et keykasutatakse lisamuutujat .

Rakenduste sortimine

Sisestussordi kasutatakse, kui:

  • massiivil on väike arv elemente
  • sortimiseks on jäänud vaid mõned elemendid

Huvitavad Artiklid...