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

Content

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

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

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

Пояснения по работе алгоритма:


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

  • Шаг 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;
}
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
MN
May 25, 2020, 11:33 a.m.
Mitja Nagibin

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
f
May 25, 2020, 5:05 a.m.
falcon

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
jm
May 25, 2020, 3:30 a.m.
just maks

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:80points,
  • Rating points4
Last comments
May 26, 2020, 6:51 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

У вас база данных не открылась Исправьте путь к базе данных на свой корректный в следующих методах void DataBase::connectToDataBase() bool DataBase::openDataBase()
T1
T1
May 26, 2020, 6:22 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

полностью повторил структору проекта. В форму дабавил tableView. Но при запуске получаю форму только с пустым tableView. Можете подсказать в чем пробелма?
May 26, 2020, 6:02 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

Потому что это файл который нужно создать, а не библиотека. В статье есть содержание этого файла. Добавляйте в проект. Копируйте содержимое из статьи.
T1
May 26, 2020, 6 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

не удается подключиить библеотеку include "database.h" выдает ошибку. Можете помочь?
Now discuss on the forum
May 26, 2020, 8:48 a.m.
Vladislav Melenchuk

Templatetags из GenericForeign

all() got an unexpected keyword argument 'content_type'
May 26, 2020, 5:16 a.m.
BlinCT

Отсутствие драйвера SQLite в пакете Qt 4 на Linux

Вот честно непонимаю почему до сих пор используют qt4, там же столько всего отсутствует, много фишек и возможностей нету там. То есть используя такое старье приходится много писать самому а не и…
DK
May 26, 2020, 2:24 a.m.
Dzhon Kofi

Disable autoscroll

такие естественные решения все перепробовал. Получилось вчера так: const int maximumScroll = ui->_samples->verticalScrollBar()->maximum();const int sliderPos = ui->_samp…
May 26, 2020, 12:43 a.m.
Ruslan Polupan

Посоветуйте новичку (базы данных и Qt, что учить)

Без БД сейчас практически никуда. Поэтому SQL надо знать. SQLite самы простой вариант, но имхо лучще начать с бд клиент-сервер. Настроить сервер. Подключаться клиентом. Просто это помогает понят…
EJ
May 25, 2020, 2:42 p.m.
Esteban José María

Компиляция пустого проекта Qt Android

qt 5.12.8 BUILD SUCCESSFUL in 42s 28 actionable tasks: 28 executed Android package built successfully in 68.251 ms. Ну, буду разбираться по-тихоньку. :)
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB