Сортировка вставками.

Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании. К положительной стороне метода относится простота реализации, а также его эффективность на частично упорядоченных последовательностях, и/или состоящих из небольшого числа элементов. Тем не менее, высокая вычислительная сложность не позволяет рекомендовать алгоритм в повсеместном использовании.

Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию (в колоде карты расположены в случайном порядке) будет следующим. Обратим внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:

  1. первая и вторая карта меньше третьей;
  2. первая и вторая карта больше третьей;
  3. первая карта уступает значением третьей, а вторая превосходит ее;
  4. первая карта превосходит значением третью карту, а вторая уступает ей.

В первом случае не происходит никаких перестановок. Во втором – вторая карта смещается на место третьей, первая на место второй, а третья карта занимает позицию первой. В предпоследнем случае первая карта остается на своем месте, в то время как вторая и третья меняются местами. Ну и наконец, последний случай требует рокировки лишь первой и третьей карт. Все последующие шаги полностью аналогичны расписанным выше.

Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.

Ниже на анимированном изображении показан еще один пример работы алгоритма сортировки вставками. Здесь, как и в предыдущем примере, последовательность сортируется по возрастанию.

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

Код программы на C++:

Код программы на Pascal:

Обе программы сортируют массив по возрастанию. В их основной части выполняются три операции: определение количества элементов в массиве, ввод этих элементов и вызов подпрограммы. Подпрограмма состоит из алгоритма сортировки и цикла, выводящего результирующую упорядоченную последовательность. Алгоритм включает в себя классическую для многих алгоритмов сортировки структуру вложенных циклов.

Количество итераций внешнего цикла не превышает n-1, где n – число элементов в массиве; внутренний цикл, начиная с шага i+1, заканчивает свое выполнение при j=0 (значение переменной-счетчика j уменьшается с каждым шагом на 1). Переменным key и temp на i-ом шаге присваиваются значения, зависящие от шага и значения элемента массива mas на этом шаге.

В переменной temp храниться значение элемента массива mas[i+1], оно во внутреннем цикле сравнивается со  значениями других элементов. Key запоминает индекс элемента, который последним был больше temp, и ему, по завершению работы внутреннего цикла, присваивается значение переменной temp.


Похожие записи:
6 Comments
  • · Edit

    key=i+1;
    var=mas[key];
    for (j=i+1; j>=0; j—)
    {
    if (var<mas[j-1])
    {
    mas[j]=mas[j-1];
    key=j-1;

    что реализовано в этом цикле и за что отвечает переменная key и var?

    Reply
    • Вся статья (в том числе и код программ) была переписана. Прочитайте ее и если возникнут вопросы, то, пожалуйста, задавайте их.

      Reply
  • Вот сортировка методом вставки, но короче(на PascalABC.NET-работает)

    Reply
  • · Edit

    4. первая карта превосходит значением третью карту, а вторая уступает ей. Такого случая не может быть потому что на данный момент в левой часть то есть первая и вторая карта отсортированы, вторая больше первой и сравниваем их с 3. А в этом случаем получается что первая больше третьей и больше второй чего не может быть. Не путайте людей исправьте пожалуйста

    Reply
  • Реально, зачем усложнять и мозги делать с key и тп
    #include
    using namespace std;

    void main()
    {
    setlocale(LC_ALL, «Rus»);
    int i, j, size, key = 0, temp = 0;
    cout << "Введите размер массива:" << endl < «;
    cin >> size;
    cout < «;
    int* arr = new int[size];
    for (i = 0; i > arr[i];
    for (i = 0; i 0; j—) {
    if (arr[j — 1] > temp) {
    temp = arr[j];
    arr[j] = arr[j — 1];
    arr[j — 1] = temp;
    }
    }
    }
    cout << endl;
    for (i = 0; i < size; i++)
    cout << arr[i] << " ";
    delete[] arr;
    }

    Reply
  • Ктонибудь при… проведите профилактическую беседу(«БЕЗ» применения силы) тем нехорошим людям, кто учит делать массивы с 1.

    Код для паскаля с необходимыми правками для массива arr длины len

    for i:=0 to len-2 do
    begin
    buf:=i+1;
    temp:=arr[buf];
    for j:=i+1 downto 1 do
    begin
    if (temp<mas[j-1]) then //
    begin
    arr[j]:=arr[j-1];
    buf:=j-1;
    assignments_count := assignments_count + 1;
    end;
    end;
    arr[buf]:=temp;
    end;

    Reply

Добавить комментарий для Андрей Отменить ответ

Your email address will not be published. Required fields are marked *