Алгоритмы сортировки данных. Сортировка вставками.

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

Program Insertion

Var A, B: array [1…1000] of integer

N, I, j: integer

Begin

{определение размера массива A(N) и его заполнения}

……………………………………………………………………………………………………

{сортировка данных}

For i: =1 to N do

Begin

J: =1

While (j> 1) and (B[j-1] > A[i]) do

Begin

B[J]: =B[j-1]

J: =j-1

End

B[j]: =A[i];

End;

{Вывод массива B}

End

Описание:

Integer – натуральные числа

Алгоритмы сортировки данных. Сортировка Шейкером.

Особенности: работает в 2 раза чем пузырёк.

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

n – количество элементов

Program Shaker Sort

Var A: array [1…1000] of integer;

N, i, j: integer;

Min, max: integer

Begin

{Определение размера массива (A – N и его заполнение)}

……………………………………………………………………………………….

{сортировка данных}

For i: =1 to n do

Begin

If A[i]> A[i+1] then

Begin

Min: =i+1;

Max: =I;

End

Else

Begin

Min: =i;

Max: =i+1;

For j: =i+2 to n-i+1 do

If A[j]> A[max] then

Max: =j

Else

If A[j]< A[min] then

Min: =I;

{обмен элементов}

P: =A[i];

A[i]: =A[min];

A[min]: =P;

If max: =I then

Max: =min

P: =A[N-i+1];

A[max]: =P;

End;

{вывод отсортированного массива А}

End

Алгоритмы сортировки данных. Быстрая сортировка.