Конспект лекций по программированию для начинающих. Гладков В.П. - 172 стр.

                                      174

    2) программы, построенные на этих методах, коротки и легки для понимания.
(следует помнить, что программы также занимают место в памяти);
    3) хотя сложные методы требуют меньшего количество операций, эти операции
более сложны, поэтому для малых n простые методы работают быстрее.
    Методы сортировки можно разбить на три основных класса в зависимости от
лежащего в их основе приема:
    1) сортировка включением (вставкой);
    2) сортировка выбором (выделением);
    3) сортировка обменом («пузырьковая сортировка»).

                       11.7.1. Сортировка включениями
    Для этой сортировки массив разделяется на две части: отсортированную и
неотсортированную. Элементы из неотсортированной части поочередно
выбираются и вставляются в отсортированную часть так, чтобы упорядоченность
этой части не нарушилась. В начале работы отсортированная часть содержит
только один элемент, а все остальные - в неотсортированной части. Таким образом,
алгоритм будет состоять из n-1 прохода (n - размерность массива), каждый из
которых будет включать следующие действия:
    - взятие первого элемента несортированной части;
    - поиск места выбранного элемента в отсортированной части: последовательное
сравнение выбранного элемента с элементами отсортированной части при
просмотре их с конца. Если элемент отсортированной части больше выбранного, то
он пересылается на одну позицию вправо, иначе выбранный элемент записывается
на свободное место в отсортированную часть.
    Рассмотрим возможную реализацию этого метода.
    n=6. Отсортированная часть отделена вертикальной чертой.
    Исходный массив a={ 3 | 1, 9, 2, 5, 7 }.
    Номера элементов: 1 2 3 4 5 6.
    Начало отсортированной части - 1, конец отсортированной части - 1.
    Начало неотсортированной части - 2, конец неотсортированной части - n.
    Первый шаг сортировки:
       выбираем первый элемент неотсортированной части: y=a[2]=1;
       сравниваем его с элементами отсортированной части, двигаясь от ее конца к
началу; поскольку а[1] > y=1, сдвигаем a[1] на одно место вправо;
       преобразованный массив a={ | 3, 9, 2, 5, 7 };
       номера элементов: 1 2 3 4 5 6;
       поскольку отсортированная часть закончилась, нужно выбранный элемент
записать в массив на свободное место; длина отсортированной части увеличилась
на 1;
       преобразованный массив a={ 1, 3 | 9, 2, 5, 7 };
       номера элементов: 1 2 3 4 5 6;
       начало отсортированной части - 1, конец отсортированной части - 2;
       Начало неотсортированной части - 3, конец неотсортированной части - n.
    Второй шаг сортировки:
       выбираем первый элемент неотсортированной части: y=a[3]=9;