Beszúrás rendezési algoritmus

Ebben az oktatóanyagban megtudhatja, hogyan működik a beillesztés rendezése. A beillesztés rendezésére működő példákat is talál C, C ++, Java és Python.

A beszúrás rendezése hasonlóan működik, mint egy kártyajátékban a kezünkben lévő kártyákat.

Feltételezzük, hogy az első kártya már rendezve van, válogatunk egy válogatatlan kártyát. Ha a nem válogatott kártya nagyobb, mint a kézben lévő kártya, akkor egyébként jobbra, balra kerül. Ugyanígy más válogatás nélküli kártyákat is vesznek, és a megfelelő helyre teszik.

Hasonló megközelítést alkalmaz a beszúrási rendezés.

A beszúrás rendezése egy rendezési algoritmus, amely egy nem rendezett elemet az iteráció megfelelő helyére helyez.

Hogyan működik a beillesztés rendezése?

Tegyük fel, hogy a következő tömböt kell rendezni.

Kezdeti tömb
  1. A tömb első elemét feltételezzük rendezve. Vegyük a második elemet, és külön tároljuk benne key.
    Hasonlítsa keyössze az első elemet. Ha az első elem nagyobb, mint key, akkor a kulcs az első elem elé kerül. Ha az első elem nagyobb, mint a kulcs, akkor a kulcs az első elem elé kerül.
  2. Most az első két elem rendezve van.
    Vegyük a harmadik elemet, és hasonlítsuk össze a tőle balra található elemekkel. Helyezze közvetlenül a nála kisebb elem mögé. Ha nincs nála kisebb elem, akkor tegye a tömb elejére. Helyezzen 1-et az elejére
  3. Hasonlóképpen tegyen minden válogatatlan elemet a megfelelő helyzetbe. Helyezzen 4 mögé 1 Helyezzen 3 mögé 1 mögé, és a tömb rendeződik

Beszúrás rendezési algoritmus

 insertionSort (tömb) jelölje meg az első elemet rendezve minden rendezetlen elemnél

Példák Python, Java és 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); )

Bonyolultság

Időkomplexumok

  • Legrosszabb bonyolultság: Tegyük fel, hogy egy tömb növekvő sorrendben van, és csökkenő sorrendben szeretné rendezni. Ebben az esetben a legrosszabb esetben komplexitás lép fel. Minden elemet össze kell hasonlítani a többi elemmel, így minden n-edik elemhez számos összehasonlítást végeznek. Így az összehasonlítások teljes száma =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Legjobb eset komplexitás: O(n)
    Ha a tömb már rendezve van, akkor a külső hurok ntöbbször fut, míg a belső hurok egyáltalán nem fut. Tehát csak nszámos összehasonlítás létezik . Így a komplexitás lineáris.
  • Átlagos esetbonyolultság: Akkor fordul elő, amikor egy tömb elemei összetévesztett sorrendben vannak (sem emelkedő, sem csökkenő).O(n2)

Tér komplexitás

A tér összetettsége O(1)azért van, mert egy extra változót keyhasználnak.

Alkalmazások beillesztése

A beszúrás rendezését akkor alkalmazzák, ha:

  • a tömbnek kevés eleme van
  • már csak néhány elem van rendezve

érdekes cikkek...