СтатьиСтатьи об алгоритмах программирования

Алгоритм сортировки перемешиванием (Шейкерная сортировка, двунаправленная пузырьковая сортировка)

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

Механизм алгоритма сортировки по возрастанию следующий:

- выбирается начало и конец диапазона массива. Причем конец массива на единицу меньше;

- выполняется последовательное сравнение и замена, выводящая большее значение в конец массива;

- сокращается диапазон обработки массива с конца на единицу;

- последовательное прохождение массива, выводящее меньшее значение в начало;

- сокращение диапазона обработки массива с начала на единицу.

Цикл завершается, когда диапазон сойдется в середине массива.

const
N = 10; // размер массива
var
i, low, high, h : Integer;
mas : array[1..N] of Integer;
begin
low := 1; // начало и конец массива
high := N - 1;

while low < high do begin
for i := low to high do // проход массива от начала к концу, перемещение большего значения
if mas[i] > mas[i+1] then begin // замена элементов местами
h := mas[i];
mas[i] := mas[i+1];
mas[i+1] := h;
end;

high := high - 1; // сокращение сортируемого диапазона от конца

for i := high downto high do // проход массива от конца к началу, перемещение меньшего значения
if mas[i] > mas[i+1] then begin // замена элементов местами
h := mas[i];
mas[i] := mas[i+1];
mas[i+1] := h;
end;

low := low + 1; // сокращение сортируемого диапазона от начала
end;
end;


Комментарии

Имя:
Текст комментария:
* В комментариях запрещено публиковать рекламные объявления. Сообщения, содержащие ссылки на сторонние ресурсы добавляется в скрытом режиме. Они будут открыты, если не нарушают установленных правил, после проверки.
Защита от спам-роботов (* Обязателельно укажите ответ на простой вопрос ниже.)
Сколько ножек у трeхногого табурета? (цифра)