Lila25mila
26 лютого 2019 р. 14:30

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

Цей опис призначений для того, щоб зрозуміти, що таке алгоритм сортування вставками та як його реалізувати у програмуванні.


Про технічні деталі, властивості та порівняння з іншим алгоритмом сортування мови тут не піде. Якщо ви знаєте, що таке алгоритм сортування вставками, відвідайте цю сторінку , щоб дізнатися про властивості сортування вставок та порівняння з іншими алгоритмами сортування.

Як працює алгоритм сортування вставок?

Пояснення щодо роботи алгоритму:


Припустимо, ви хочете відсортувати елементи зростання, як показано на малюнку вище. Тоді виконуються такі кроки:

Крок 1: Другий елемент масиву порівнюється з елементами, які з'являються перед ним (в даному випадку тільки перший елемент). Якщо другий елемент менший за перший елемент, другий елемент вставляється в позицію першого елемента. Після першого кроку перші два елементи масиву будуть відсортовані.
Крок 2: Третій елемент масиву порівнюється з елементами, які з'являються перед ним (перший та другий елемент). Якщо третій елемент менший за перший, він вставляється в позицію першого елемента. Якщо третій елемент більший за перший елемент, але менший за другий елемент, він вставляється в позицію другого елемента. Якщо третій елемент більше, ніж обидва елементи, він залишається в тому самому положенні. Після другого кроку перші три елементи масиву будуть відсортовані.
Крок 3: Аналогічно, четвертий елемент масиву порівнюється з елементами, які з'являються перед ним (перший, другий і третій елемент), і застосовується та сама процедура, і цей елемент вставляється в правильне положення. Після третього кроку перші чотири елементи масиву будуть відсортовані.

Якщо є n елементів для сортування, ця процедура повторюється n-1 раз, щоб вийшов відсортований список масивів.

Елементи сортування програми C з використанням вставного алгоритму сортування
  1. /*Сортировка элементов массива в порядке возрастания с использованием алгоритма сортировки вставками*/
  2. #include<stdio.h>
  3. int main()
  4. {
  5. int data[100],n,temp,i,j;
  6. printf("Enter number of terms(should be less than 100): ");
  7. scanf("%d",&n);
  8. printf("Enter elements: ");
  9. for(i=0;i<n;i++)
  10. {
  11. scanf("%d",&data[i]);
  12. }
  13. for(i=1;i<n;i++)
  14. {
  15. temp = data[i];
  16. j=i-1;
  17. while(temp<data[j] && j>=0)
  18. /*Чтобы отсортировать элементы в порядке убывания, измените temp <data [j] на temp> data [j] в строке выше.*/
  19. {
  20. data[j+1] = data[j];
  21. --j;
  22. }
  23. data[j+1]=temp;
  24. }
  25. printf("In ascending order: ");
  26. for(i=0; i<n; i++)
  27. printf("%d\t",data[i]);
  28. return 0;
  29. }

Примітка: хоча ця програма написана мовою C, алгоритм сортування вставками можна аналогічним чином використовувати й інших мов програмування.

Виведення на екран:

  1. Enter number of terms(should be less than 100): 5
  2. Enter elements: 12
  3. 1
  4. 2
  5. 5
  6. 3
  7. In ascending order: 1 2 3 5 12

Ще один вихідний код, який використовує ту ж техніку алгоритму сортування вставки для сортування елементів масиву.

  1. / * Этот исходный код также является реализацией алгоритма сортировки вставками для сортировки элементов массива. * /
  2. / * Эта программа немного сложна, поскольку содержит несколько циклов. * /
  3. / * Программа для сортировки массива в порядке убывания * /
  4. #include <stdio.h>
  5. int main()
  6. {
  7. int data[100],n,i,j,hold,k;
  8. printf("Enter number of terms(should be less than 100): ");
  9. scanf("%d",&n);
  10. printf("Enter elements: ");
  11. for(i=0;i<=n-1;++i)
  12. {
  13. scanf("%d",&data[i]);
  14. }
  15. for(i=1;i<=n-1;++i)
  16. {
  17. for(j=0;j<i;++j)
  18. if(data[j]<data[i])
  19. / * Чтобы отсортировать элементы в порядке возрастания, измените <на> в строке выше. * /
  20. {
  21. hold=data[i];
  22. k=i;
  23. while(k!=j)
  24. {
  25. data[k]=data[k-1];
  26. --k;
  27. }
  28. data[j]=hold;
  29. }
  30. }
  31. printf("In descending Order: ");
  32. for(i=0;i<=n-1;++i)
  33. {
  34. printf("%d ",data[i]);
  35. }
  36. return 0;
  37. }

По статті запитували0питання

2

Вам це подобається? Поділіться в соціальних мережах!

Коментарі

Only authorized users can post comments.
Please, Log in or Sign up