Įterpimo rūšiavimo algoritmas

Šioje pamokoje sužinosite, kaip veikia įterpimo rūšiavimas. Taip pat rasite veikiančių įterpimo rūšiavimo pavyzdžių C, C ++, Java ir Python.

Įterpimo rūšiavimas veikia panašiai, kaip kortų žaidime mes rūšiuojame kortas rankoje.

Manome, kad tada jau surūšiuota pirmoji kortelė, mes pasirenkame nerūšiuotą kortelę. Jei nerūšiuota kortelė yra didesnė už kortelę, kuri yra rankoje, ji dedama dešinėje, kitaip, kairėje. Lygiai taip pat imamos kitos nerūšiuotos kortelės ir dedamos į reikiamą vietą.

Panašus metodas naudojamas įterpiant rūšiavimą.

Įterpimo rūšiavimas yra rūšiavimo algoritmas, kuris nerūšiuotą elementą pateikia kiekvienoje iteracijoje jam tinkamoje vietoje.

Kaip veikia įterpimo rūšiavimas?

Tarkime, turime surūšiuoti šį masyvą.

Pradinis masyvas
  1. Laikoma, kad pirmasis masyvo elementas yra rūšiuojamas. Paimkite antrąjį elementą ir laikykite jį atskirai key.
    Palyginkite keysu pirmuoju elementu. Jei pirmasis elementas yra didesnis nei key, tada raktas dedamas priešais pirmąjį elementą. Jei pirmasis elementas yra didesnis nei raktas, raktas dedamas priešais pirmąjį elementą.
  2. Pirmieji du elementai yra rūšiuojami.
    Paimkite trečią elementą ir palyginkite su jo kairėje esančiais elementais. Padėjo jį už mažesnio už jį elemento. Jei nėra mažesnio už jį elemento, įdėkite jį į masyvo pradžią. Pradžioje padėkite 1
  3. Panašiai padėkite kiekvieną nerūšiuotą elementą teisingoje padėtyje. 4 vieta už 1 Vieta 3 už 1 ir masyvas rūšiuojamas

Įterpimo rūšiavimo algoritmas

 „insertionSort“ (masyvas) pažymėkite pirmąjį elementą kaip surūšiuotą kiekvienam nerūšiuotam elementui X „ištraukite“ elementą X, skirtą j X, perkelkite rūšiuojamą elementą į dešinę 1 pertraukos kilpa ir įterpkite X čia, baigdami įterpimą

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Sudėtingumas

Laiko kompleksiškumas

  • Blogiausio atvejo sudėtingumas: Tarkime, masyvas yra didėjimo tvarka ir norite jį rūšiuoti mažėjimo tvarka. Šiuo atveju blogiausias atvejis būna sudėtingas. Kiekvienas elementas turi būti lyginamas su visais kitais elementais, todėl kiekvienam n-ajam elementui atliekama daugybė palyginimų. Taigi bendras palyginimų skaičius =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Geriausio atvejo sudėtingumas: O(n)
    Kai masyvas jau yra rūšiuojamas, išorinė kilpa eina nkelis kartus, o vidinė - visiškai neveikia. Taigi, yra tik nkeletas palyginimų. Taigi, sudėtingumas yra tiesinis.
  • Vidutinis atvejo sudėtingumas: Tai įvyksta, kai masyvo elementai yra susimaišę (nei didėjant, nei mažėjant).O(n2)

Erdvės sudėtingumas

Erdvė yra sudėtinga, O(1)nes naudojamas papildomas kintamasis key.

Įterpimo rūšiavimo programos

Įterpimo rūšiavimas naudojamas, kai:

  • masyvas yra nedaug elementų
  • liko tik keli elementai, kuriuos reikia išrūšiuoti

Įdomios straipsniai...