Алгоритм сортировки вставкой

В этом руководстве вы узнаете, как работает сортировка вставкой. Также вы найдете рабочие примеры сортировки вставкой в C, C ++, Java и Python.

Сортировка вставкой работает аналогично сортировке карт в руке в карточной игре.

Предполагаем, что первая карта уже отсортирована, тогда выбираем несортированную карту. Если неотсортированная карта больше, чем карта в руке, она помещается справа, в противном случае - слева. Таким же образом берутся и другие неотсортированные карты и кладут на свои места.

Похожий подход используется сортировкой вставкой.

Сортировка вставкой - это алгоритм сортировки, который помещает несортированный элемент в подходящее место на каждой итерации.

Как работает сортировка вставкой?

Предположим, нам нужно отсортировать следующий массив.

Исходный массив

Предполагается, что первый элемент массива отсортирован. Возьмите второй элемент и храните отдельно в key.
Сравните keyс первым элементом. Если первый элемент больше чем key, то ключ помещается перед первым элементом. Если первый элемент больше, чем key, то key помещается перед первым элементом.
Теперь первые два элемента отсортированы.
Возьмите третий элемент и сравните его с элементами слева от него. Поместите его сразу за элементом меньшего размера. Если нет меньшего элемента, поместите его в начало массива. Поместите 1 в начало
Точно так же поместите каждый неотсортированный элемент в правильное положение. Поместите 4 за 1 Поместите 3 за 1, и массив будет отсортирован

Алгоритм сортировки вставкой

 InsertSort (array) помечает первый элемент как отсортированный для каждого несортированного элемента X 'извлекает' элемент X для j X перемещает отсортированный элемент вправо на 1 цикл разрыва и вставляет X здесь end insertSort

Примеры 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²)