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

алгоритм, сортировка, Sort Algorithm

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

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

Как работает алгоритм сортировки вставок?

Пояснения по работе алгоритма:
Предположим, вы хотите отсортировать элементы по возрастанию, как показано на рисунке выше. Тогда выполняются следующие шаги:

  • Шаг 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;
}
Виртуальный хостинг со скидкой 10 процентов
Виртуальный хостинг со скидкой 10 процентов
EVILEG предлагает надёжный хостинг со скидкой 10% на виртуальный хостинг и 5% на VPS

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
s
26 мая 2019 г. 14:33
simpleunderground

Qt - Тест 001. Сигналы и слоты

  • Результат:31баллов,
  • Очки рейтинга-10
НД
25 мая 2019 г. 23:25
Николай Демиденко

C++ - Тест 003. Условия и циклы

  • Результат:64баллов,
  • Очки рейтинга-1
НД
25 мая 2019 г. 23:19
Николай Демиденко

C++ - Тест 002. Константы

  • Результат:50баллов,
  • Очки рейтинга-4
Последние комментарии
21 мая 2019 г. 20:10
Дмитрий

Приветствую! Я думаю дойдёт и до этого, но пока изучать его у меня нет желания.
20 мая 2019 г. 19:20
Евгений Легоцкой

Добрый день! Вы не думали разместить репозиторий проекта на GitHub?
P.
18 мая 2019 г. 14:03
PELMYACH .

Спасибо большое! Вскоре буду разбираться!
18 мая 2019 г. 9:13
Евгений Легоцкой

Добрый день! Отнимать значение общего счётчика можно в деструкторе класса кнопки QDynamicButton::~QDynamicButton(){ ResID--;} При этом я бы ещё переустанавливал значения вс...
P.
14 мая 2019 г. 22:33
PELMYACH .

Здравствуйте!А не подскажите, как можно при удалении какой либо кнопки, у щётчика отнять значение?Дабы например четвёртой кнопке соответствовал ID 4, а не 5 скажем
Сейчас обсуждают на форуме
26 мая 2019 г. 6:49
Михаиллл

Скачал dll от сюда и заработало
24 мая 2019 г. 6:48
Евгений Легоцкой

Если там будут только перечисления внутри namespace, то жа, достаточно будет заголовочного файла
24 мая 2019 г. 6:28
Андрей Янкович

работает любой http сервер, и можно использовать обсалютно любой портпример <RemoteRepositories> <Repository> <Url>http://178.124.160.6:3030/A/B&l...;
23 мая 2019 г. 10:42
Михаиллл

Спасибо, помогло.
23 мая 2019 г. 6:31
Евгений Легоцкой

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

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB