Цей опис призначений для того, щоб зрозуміти, що таке алгоритм сортування вставками та як його реалізувати у програмуванні.
Про технічні деталі, властивості та порівняння з іншим алгоритмом сортування мови тут не піде. Якщо ви знаєте, що таке алгоритм сортування вставками, відвідайте цю сторінку , щоб дізнатися про властивості сортування вставок та порівняння з іншими алгоритмами сортування.
Як працює алгоритм сортування вставок?
Пояснення щодо роботи алгоритму:
Припустимо, ви хочете відсортувати елементи зростання, як показано на малюнку вище. Тоді виконуються такі кроки:
Крок 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;
- }