Algoritem razvrščanja vstavkov

V tej vadnici boste izvedeli, kako deluje razvrščanje vstavljanja. Prav tako boste našli delovne primere razvrščanja vstavljanja v C, C ++, Java in Python.

Razvrstitev vstavkov deluje podobno, kot če v igri s kartami razvrščamo karte v roki.

Predvidevamo, da je prva kartica že razvrščena, nato izberemo nesortirano. Če je nesortirana karta večja od karte v roki, se postavi na desno, sicer na levo. Na enak način se vzamejo druge nesortirane karte in jih postavijo na svoje pravo mesto.

Podoben pristop se uporablja pri vstavljanju.

Razvrstitev pri vstavljanju je algoritem za razvrščanje, ki nesortirani element postavi na njegovo primerno mesto v vsaki ponovitvi.

Kako deluje sortiranje vstavljanja?

Recimo, da moramo razvrstiti naslednjo matriko.

Začetno polje
  1. Predpostavlja se, da je prvi element v matriki razvrščen. Vzemite drugi element in ga shranite ločeno key.
    Primerjaj keys prvim elementom. Če je prvi element večji od key, je ključ postavljen pred prvi element. Če je prvi element večji od ključa, je ključ postavljen pred prvi element.
  2. Zdaj sta prva dva elementa razvrščena.
    Vzemite tretji element in ga primerjajte z elementi na levi strani. Postavljen je tik za element, ki je manjši od njega. Če ni elementa, ki je manjši od njega, ga postavite na začetek polja. Postavite 1 na začetek
  3. Podobno postavite vsak nerazvrščen element na svoj pravilen položaj. Mesto 4 za 1 Mesto 3 za 1 in niz je razvrščen

Algoritem razvrščanja vstavkov

 insertionSort (matrika) označi prvi element kot razvrščen za vsak nerazvrščen element X 'izvleči' element X za j X premakni razvrščeni element v desno za 1 prekinitveno zanko in vstavi X sem konec insertionSort

Primeri Python, Java in C / C ++

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

Kompleksnost

Časovne zapletenosti

  • Najslabša zapletenost: Recimo, da je matrika v naraščajočem vrstnem redu in jo želite razvrstiti po padajočem vrstnem redu. V tem primeru pride do najslabše zapletenosti. Vsak element je treba primerjati z vsakim drugim elementom, zato je za vsak n-ti element narejeno število primerjav. Tako je skupno število primerjav =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Najboljša zapletenost: O(n)
    Ko je polje že razvrščeno, se zunanja zanka izvaja nvečkrat, notranja pa se sploh ne zažene. Torej, nprimerjav je le veliko. Tako je kompleksnost linearna.
  • Povprečna zapletenost primerov: Pojavi se, če so elementi matrike v vrstnem redu (niti naraščajoče niti padajoče).O(n2)

Zapletenost prostora

Zapletenost prostora je O(1)zato, ker se uporablja dodatna spremenljivka key.

Aplikacije za razvrščanje po vstavitvi

Razvrstitev vstavljanja se uporablja, kadar:

  • matrika ima majhno število elementov
  • razvrščenih je le nekaj elementov

Zanimive Članki...