Это описание предназначено для того, чтобы понять, что такое алгоритм сортировки вставками и как его реализовать в программировании.
О технических деталях, свойствах и сравнении с другим алгоритмом сортировки речи здесь не пойдет. Если вы знаете, что такое алгоритм сортировки вставками, посетите эту страницу , чтобы узнать о свойствах сортировки вставок и сравнения с другими алгоритмами сортировки.
Как работает алгоритм сортировки вставок?
Пояснения по работе алгоритма:
Предположим, вы хотите отсортировать элементы по возрастанию, как показано на рисунке выше. Тогда выполняются следующие шаги:
- Шаг 1: Второй элемент массива сравнивается с элементами, которые появляются перед ним (в данном случае только первый элемент). Если второй элемент меньше первого элемента, второй элемент вставляется в позицию первого элемента. После первого шага, первые два элемента массива будут отсортированы.
- Шаг 2: Третий элемент массива сравнивается с элементами, которые появляются перед ним (первый и второй элемент). Если третий элемент меньше первого, он вставляется в позицию первого элемента. Если третий элемент больше первого элемента, но меньше второго элемента, он вставляется в позицию второго элемента. Если третий элемент больше, чем оба элемента, он остается в том же положении. После второго шага первые три элемента массива будут отсортированы.
- Шаг 3: Аналогично, четвертый элемент массива сравнивается с элементами, которые появляются перед ним (первый, второй и третий элемент), и применяется та же процедура, и этот элемент вставляется в правильное положение. После третьего шага первые четыре элемента массива будут отсортированы.
Если есть n элементов для сортировки, то эта процедура повторяется n-1 раз, чтобы получился отсортированный список массивов.
Элементы сортировки программы C с использованием вставного алгоритма сортировки
/*Сортировка элементов массива в порядке возрастания с использованием алгоритма сортировки вставками*/
#include<stdio.h>
int main()
{
int data[100],n,temp,i,j;
printf("Enter number of terms(should be less than 100): ");
scanf("%d",&n);
printf("Enter elements: ");
for(i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
for(i=1;i<n;i++)
{
temp = data[i];
j=i-1;
while(temp<data[j] && j>=0)
/*Чтобы отсортировать элементы в порядке убывания, измените temp <data [j] на temp> data [j] в строке выше.*/
{
data[j+1] = data[j];
--j;
}
data[j+1]=temp;
}
printf("In ascending order: ");
for(i=0; i<n; i++)
printf("%d\t",data[i]);
return 0;
}
Примечание: хотя эта программа написана на языке C, алгоритм сортировки вставками можно аналогичным образом использовать и в других языках программирования.
Вывод на экран:
Enter number of terms(should be less than 100): 5 Enter elements: 12 1 2 5 3 In ascending order: 1 2 3 5 12
Вот еще один исходный код, который использует ту же технику алгоритма сортировки вставки для сортировки элементов массива.
/ * Этот исходный код также является реализацией алгоритма сортировки вставками для сортировки элементов массива. * /
/ * Эта программа немного сложна, поскольку содержит несколько циклов. * /
/ * Программа для сортировки массива в порядке убывания * /
#include <stdio.h>
int main()
{
int data[100],n,i,j,hold,k;
printf("Enter number of terms(should be less than 100): ");
scanf("%d",&n);
printf("Enter elements: ");
for(i=0;i<=n-1;++i)
{
scanf("%d",&data[i]);
}
for(i=1;i<=n-1;++i)
{
for(j=0;j<i;++j)
if(data[j]<data[i])
/ * Чтобы отсортировать элементы в порядке возрастания, измените <на> в строке выше. * /
{
hold=data[i];
k=i;
while(k!=j)
{
data[k]=data[k-1];
--k;
}
data[j]=hold;
}
}
printf("In descending Order: ");
for(i=0;i<=n-1;++i)
{
printf("%d ",data[i]);
}
return 0;
}
