Сортировка вставками: алгоритм с C, C++, Java, Python Примеры
Сара Чен
Что такое сортировка вставками?
Сортировка вставками — это один из алгоритмов сортировки сравнением, используемый для сортировки элементов путем итерации по одному элементу за раз и размещения элемента в правильном положении.
Каждый элемент последовательно вставляется в уже отсортированный список. Размер уже отсортированного списка изначально равен единице. Алгоритм сортировки вставками гарантирует, что первые k элементов будут отсортированы после k-й итерации.
Характеристики алгоритма сортировки вставками
Алгоритм сортировки вставками имеет следующие важные характеристики:
- Это стабильный метод сортировки, поэтому он не меняет относительный порядок равных элементов.
- Это эффективно для небольших наборов данных, но неэффективно для больших списков.
- Сортировка вставками является адаптивной, что уменьшает общее количество шагов, если она частично отсортирована. массив предоставляется в качестве входных данных, чтобы сделать его эффективным.
Как работает вставка Operaционная работа?
В алгоритме сортировки вставками операция вставки используется для сортировки неотсортированных элементов. Это помогает вставить новый элемент в уже отсортированный список.
Псевдокод операции вставки:
Рассмотрим список A из N элементов.
A[N-1] is the element to be inserted in the sorted sublist A[0..N-2]. For i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else Stop
В приведенном выше примере новый элемент 6 должен быть вставлен в уже отсортированный список.
Шаг 1) По сравнению с соседним слева элементом A[5], 9 > 6, мы меняем местами позиции 9 и 6. Теперь элемент 6 перемещается в A[4].
Шаг 2) Теперь мы сравниваем A[4] и A[3] и обнаруживаем, что A[3] > A[4], мы снова меняем местами позиции 6 и 8.
Шаг 3) Теперь сравните A[3] и A[2], поскольку A[2] > A[3] меняют местами 7 и 6.
Шаг 4) Мы сравниваем A[1] и A[2], причем A[1] < A[2], т. е. левый соседний элемент больше не больше. Теперь делаем вывод, что 6 вставлено правильно, и останавливаем алгоритм на этом.
Как работает сортировка вставками
Операция вставки, описанная выше, является основой сортировки вставкой. Процедура вставки выполняется для каждого элемента, и в итоге мы получаем отсортированный список.
На приведенном выше примере демонстрируется работа сортировки вставкой в структуру данных. Первоначально в отсортированном подсписке присутствует только один элемент, т. е. 4. После вставки A[1], т. е. 3, размер отсортированного подсписка увеличивается до 2.
C++ Программа для сортировки вставками
#include <iostream>
using namespace std;
int main(){
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
cout << "\nUnsorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
int current_element,temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
cout << "\nSorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
return 0;
}
Вывод:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Код C для сортировки вставками
#include <stdio.h>
int main() {
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
printf("\nUnsorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
int current_element, temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
printf("\nSorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
return 0;
}
Вывод:
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python Программа для сортировки вставками
#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]
#size of list
size_unsorted = len(unsorted)
#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
for i in range(1, size_unsorted):
current_element = unsorted[i]
j = i - 1
while j >= 0 and unsorted[j] > current_element:
#swapping if current element is lesser
unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
j -= 1
#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
Вывод:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Свойства сортировки вставками
Вот важные свойства сортировки вставками:
- В сети: Сортировка вставкой может сортировать элементы по мере их получения. То есть, если мы уже отсортировали список элементов и добавили в списки еще какие-то элементы, то нам не нужно запускать всю процедуру сортировки заново. Вместо этого нам нужно перебирать только вновь добавленные элементы.
- На месте: Пространственная сложность алгоритма сортировки вставками постоянна и не требует дополнительного места. Этот алгоритм сортирует элементы на месте.
- Стабильная: При сортировке вставками мы не меняем местами элементы, если их значения равны. Например, два элемента x и y равны, и x появляется перед y в несортированных списках, тогда в отсортированном списке x появляется перед y. Это делает сортировку вставкой стабильной.
- Адаптивный: A алгоритм сортировки является адаптивным, если требуется меньше времени, если входные элементы или подмножество элементов уже отсортированы. Как мы обсуждали выше, лучшее время выполнения сортировки вставкой — O(N), а худшее — O(N^2). Сортировка вставками — один из адаптивных алгоритмов сортировки.
Сложность сортировки вставками
Космическая сложность
Сортировка вставками не требует дополнительного пространства для сортировки элементов, сложность пространства постоянна, т. е. O(1).
Сложность времени
Поскольку сортировка вставками обрабатывает каждый элемент одновременно, для сортировки N элементов требуется N-1 проход. Для каждого прохода он может делать нулевые замены, если элементы уже отсортированы, или менять местами, если элементы расположены в порядке убывания.
- Для прохода 1 минимальное необходимое количество свопов равно нулю, а максимальное необходимое количество свопов равно 1.
- Для прохода 2 минимальное необходимое количество свопов равно нулю, а максимальное необходимое количество свопов равно 2.
- Для прохода N минимальный требуемый обмен равен нулю, а максимальный требуемый обмен равен N.
- Минимальная замена равна нулю, поэтому наилучшая временная сложность равна O(N) для итерации N проходов.
- Общие максимальные свопы составляют (1+2+3+4+..+N) i. N(N+1)/2, худшая временная сложность — O(N^2).
Вот важная временная сложность сортировки вставкой:
- Наихудшая сложность случая: O(n2): Сортировка массива по убыванию, когда он находится в порядке возрастания, является наихудшим сценарием.
- лучшая сложность дела: O(n): лучший Случай Сложность возникает, когда массив уже отсортирован, внешний цикл выполняется n раз, а внутренний цикл не выполняется вообще. Имеется только n сравнений. Таким образом, в этом случае сложность линейна.
- Средняя сложность дела: O(n2): Это происходит, когда элементы массива располагаются в перемешанном порядке, который не является ни возрастающим, ни убывающим.
Резюме
- Сортировка вставками — это метод алгоритма сортировки, основанный на сравнении.
- Это стабильный метод сортировки, поэтому он не меняет относительный порядок равных элементов.
- Для каждого элемента операция вставки используется для вставки элемента в отсортированный подсписок.
- Сортировка вставками — это алгоритм сортировки на месте.
- Наихудшая и средняя временная сложность сортировки вставками является квадратичной, т. е. O(N^2).
- Сортировка вставками не требует вспомогательного пространства.
