Сортировка вставки

Сортировка вставки в C-это простой и эффективный алгоритм сортировки, который создает окончательный сортированный массив по одному элементу за раз. Обычно он реализуется, когда у пользователя есть небольшой набор данных.

Что такое Тип вставки?

Сортировка вставки — это алгоритм сортировки, при котором массив сортируется путем взятия одного элемента за раз. Принцип сортировки вставки состоит в том, чтобы взять один элемент, перебрать отсортированный массив и найти его правильное положение в отсортированном массиве. Принцип работы сортировки вставки такой же, как при раскладывании колоды карт по масти.

Краткая работа и сложность

На каждой итерации он сравнивает текущий элемент со значениями в отсортированном массиве. Если текущий элемент больше, чем элемент в массиве, то он покидает элемент и переходит к следующему элементу массива. В противном случае, если текущий элемент меньше элемента массива, то он перемещает остальную часть элемента в массиве на одну позицию и освобождает место для текущего в отсортированном массиве.

Таким образом, сортировка вставки берет по одному входному элементу за раз, перебирает сортированный суб-массив и с каждой итерацией вставляет один элемент в его правильное положение. Вот почему алгоритм известен как сортировка вставки.

Поскольку средняя и наихудшая сложность этого алгоритма равны O(n2), где n-количество элементов, сортировка вставки не подходит для больших наборов данных.

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

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

Чтобы понять, как работает сортировка вставки, обратитесь к приведенным ниже таблицам.

Давайте разберемся, как работает сортировка вставки по приведенным выше таблицам.

122, 17, 93, 3, 36

for i = 1(2-й элемент) — 36 (последний элемент)

i = 1. Поскольку 17 меньше 122, переместите 122 и вставьте 17 перед 122

17, 122, 93, 3, 36

i = 2. Поскольку 93 меньше 122, переместите 122 и вставьте 93 перед 122

17, 93,122, 3, 36

i = 3. 3 переместится в начало, а все остальные элементы от 17 до 122 переместятся на одну позицию впереди своего текущего положения.

3, 17, 93, 122, 36

i = 4. 36 переместится на позицию после 17, а элементы от 93 до 122 переместятся на одну позицию впереди своей текущей позиции.

3, 17, 36, 93 ,122

Теперь, когда мы поняли, как работает сортировка вставки, давайте быстро рассмотрим код C для реализации сортировки вставки

Функция сортировки вставки

voidinsertionSort(int array[], int n)
{
int i, element, j;
for (i = 1; i < n; i++) { element = array[i]; j = i — 1; /* Переместить элементы из массива[0..i-1], которые больше ключевого значения на один*/ while (j >= 0 && array[j] > element) {
array[j + 1] = array[j];
j = j — 1;
}
array[j + 1] = element;
}
}

Сортировка вставки в C: Код

#include<math.h>
#include <stdio.h>

// Функция Сортировки Вставки
voidinsertionSort(int array[], intn)
{
inti, element, j;
for (i = 1; i < n; i++) { element = array[i]; j = i — 1; while (j >= 0 && array[j] > element) {
array[j + 1] = array[j];
j = j — 1;
}
array[j + 1] = element;
}
}
// Функция для печати элементов массива
voidprintArray(intarray[], intn)
{
int i;
for (i = 0; i < n; i++)
printf(«%d «, array[i]);
printf(«n»);
}

Еще один вариант написания кода:

#include <stdio.h>
// функция для печати элементов массива
voiddisplay(intarr[], intn) {
for (int i = 0; i < n; i++) {
printf(«%d «, arr[i]);
}
printf(«\n»);
}
// функция сортировки элементов массива
voidinsertionSort(intarr[], int n) {
for (int i = 1; i < n; i++) {
inttmp = arr[i];
int j = i — 1;

while (tmp<arr[j] && j >= 0) {
arr[j + 1] = arr[j];
—j;
}
arr[j + 1] = tmp;
}
}
// основная функция
intmain() {
intarr[] = {9, 5, 1, 4, 3};
intn = sizeof(arr) / sizeof(arr[0]);
printf(«Элементы перед сортировкой:\n»);
display(arr, n);
insertionSort(arr, n);
printf(«Элементы после сортировки:\n»);
display(arr, n);
}

Выход:

Элементы перед сортировкой:
9 5 1 4 3
Элементы после сортировки:
1 3 4 5 9

Заключение

Теперь, выполнив приведенные выше программы на языке Си, вы поняли, как работает сортировка вставки и как ее реализовать.