Алгоритм сортування вставки

У цьому посібнику ви дізнаєтесь, як працює сортування вставки. Крім того, ви знайдете робочі приклади сортування вставки у C, C ++, Java та Python.

Сортування вставки працює подібно до того, як ми сортуємо карти в руці в картковій грі.

Припускаємо, що перша картка вже відсортована, тоді ми вибираємо невідсортовану карту. Якщо невідсортована картка перевищує карту в руці, вона розміщується праворуч, ліворуч. Таким же чином беруть інші невідсортовані картки і ставлять їх на потрібне місце.

Подібний підхід використовується за допомогою вставки сортування.

Сортування вставки - це алгоритм сортування, який розміщує несортований елемент у відповідному місці в кожній ітерації.

Як працює сортування вставки?

Припустимо, нам потрібно відсортувати наступний масив.

Початковий масив

Перший елемент масиву вважається відсортованим. Візьміть другий елемент і зберігайте його окремо в key.
Порівняйте keyз першим елементом. Якщо перший елемент більше ніж key, тоді ключ розміщується перед першим елементом. Якщо перший елемент більший за ключ, то ключ розміщується перед першим елементом.
Тепер перші два елементи відсортовані.
Візьміть третій елемент і порівняйте його з елементами зліва від нього. Розмістив його відразу за елементом, меншим за нього. Якщо немає елемента, меншого за нього, розмістіть його на початку масиву. Місце 1 на початку
Подібним чином розмістіть кожен несортований елемент у правильному положенні. Місце 4 позаду 1 Місце 3 позаду 1 і масив відсортовано

Алгоритм сортування вставки

 insertionSort (масив) позначити перший елемент як відсортований для кожного невідсортованого елемента X 'витягнути' елемент X для j X перемістити відсортований елемент вправо на 1 цикл розриву та вставити сюди X кінець 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(n²)

(n-1)
n*(n-1) ~ n²
Складність найкращого випадку: O(n)
Коли масив вже відсортований, зовнішній цикл запускається nстільки разів, тоді як внутрішній цикл взагалі не працює. Отже, існує лише nкількість порівнянь. Таким чином, складність лінійна.
Середня складність справи: Це відбувається, коли елементи масиву розташовані в порядку перемішування (ні за зростанням, ні за спаданням).O(n²)