Алгоритъм за сортиране при вмъкване

В този урок ще научите как работи сортирането при вмъкване. Също така ще намерите работещи примери за сортиране на вмъкване в C, C ++, Java и Python.

Сортирането по вмъкване работи по същия начин, както сортираме картите в ръка в игра с карти.

Предполагаме, че първата карта вече е сортирана, тогава избираме несортирана карта. Ако несортираната карта е по-голяма от картата в ръка, тя се поставя вдясно в противен случай, вляво. По същия начин се вземат и други несортирани карти и се поставят на правилното им място.

Подобен подход се използва чрез сортиране на вмъкване.

Сортирането при вмъкване е алгоритъм за сортиране, който поставя несортиран елемент на подходящото място във всяка итерация.

Как работи сортирането при вмъкване?

Да предположим, че трябва да сортираме следния масив.

Първоначален масив
  1. Предполага се, че първият елемент в масива е сортиран. Вземете втория елемент и го съхранявайте отделно key.
    Сравнете keyс първия елемент. Ако първият елемент е по-голям от key, тогава ключът се поставя пред първия елемент. Ако първият елемент е по-голям от ключ, тогава ключът се поставя пред първия елемент.
  2. Сега първите два елемента са сортирани.
    Вземете третия елемент и го сравнете с елементите вляво от него. Поставен е точно зад елемента, по-малък от него. Ако няма елемент по-малък от него, тогава го поставете в началото на масива. Поставете 1 в началото
  3. По същия начин поставете всеки несортиран елемент в правилната му позиция. Поставете 4 зад 1 Поставете 3 зад 1 и масивът е сортиран

Алгоритъм за сортиране при вмъкване

 insertionSort (масив) маркира първия елемент като сортиран за всеки несортиран елемент X „извлича“ елемента X за j X премества сортирания елемент надясно с 1 цикъл на прекъсване и вмъква X тук end insertionSort

Примери за Python, Java и 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); )

Сложност

Сложни времена

  • Най-лошият сложен случай: Да предположим, че масивът е във възходящ ред и искате да го сортирате в низходящ ред. В този случай възниква най-лошият сложен случай. Всеки елемент трябва да се сравнява с всеки от другите елементи, така че за всеки n-ти елемент се правят сравнения. По този начин общият брой сравнения =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Най-добрата сложност: O(n)
    Когато масивът вече е сортиран, външният цикъл се изпълнява nняколко пъти, докато вътрешният цикъл изобщо не се изпълнява. И така, има само nброй сравнения. По този начин сложността е линейна.
  • Средна сложност на случая: Това се случва, когато елементите на масив са в объркан ред (нито възходящ, нито низходящ).O(n2)

Сложност на пространството

Сложността на пространството е O(1)защото се използва допълнителна променлива key.

Приложения за сортиране по вмъкване

Сортирането на вмъкването се използва, когато:

  • масивът има малък брой елементи
  • остават само няколко елемента за сортиране

Интересни статии...