Сортировка подсчетом

Этот простой и легкий для понимания метод заключается в том, что каждый элемент массива сравнивается со всеми остальными. Место каждого элемента в отсортированном массиве зависит от числа элементов, меньших его.

Иными словами, если некоторый элемент превышает 13 других, то его место в упорядоченной последовательности — 14. Следовательно, для сортировки необходимо сравнить попарно все элементы и подсчитать, сколько из них меньше каждого отдельного элемента.

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

Используются следующие величины:

i — индекс рассматриваемого элемента;

j — индекс элемента, с которым сравнивается рассматриваемый;

k — число элементов, меньших рассматриваемого.

Процедуры, выполняющие сортировку массива a методом подсчета и заполняющая отсортированными элементами массив b:

procedure Count_Sort(a:arrtype;var b: arrtype);

var i, j, k: integer;

begin

for i:=l to n do {Для каждого элемента массива а определяем }

begin { величину k сравнивая его со всеми }

k:=0;

for j:=1 to i-1 do

if a[j]<a[i] then k:=k+l;

for j:=i+l to n {остальными элементами) do

if a[j]<a[i] then k:=k+l;

{ Размещаем элемент a[i] на k+1 месте в массиве b}

b[k+l]:=a[i]

end;

end;

Алгоритм сортировки вставками (метод прямого включения)

Сортировка вставками (используется также термин "включениями"), так же как и сортировка методов простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.

Сортировка методом прямого включения, как и все описанные выше, производится по шагам.

На k-м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть a[1] < a[2]< ... < a[k-l].

Далее необходимо взять k-й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое j (1<=j<=k-1), что a[j ]<=a[k].

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

Метод вставки в каком-то смысле противоположен методу выбора, так как здесь просматриваются все элементы «готового» массива и только один элемент из исходной последовательности.

4 5 2 1 3

4 5 2 1 3

4 5 2 1 3

2 4 5 1 3

1 2 4 5 3

1 2 3 4 5

Сортировку вставками рассмотрим на примере следующей неупорядоченной последовательности элементов: {38, 12, 80, 15, 36, 23, 74, 62}.

Методику сортировки иллюстрирует рис. 1, где (для каждого этапа) справа указан очередной элемент, а стрелкой сверху отмечено место перемещения (при необходимости) этого элемента.

1-й этап 38 (l2) 80 15 36 23 74 62

2-й этап 12 38 (80) 15 36 23 74 62

3-й этап 12 38 80 (15) 36 23 74 62

4-й этап 12 15 38 80 (36) 23 74 62

5-й этап 12 15 36 З8 80 (23) 74 62

6-й этап 12 15 23 36 38 80 (74) 62

7-й этап 12 15 23 36 38 74 80 (62)

12 15 23 36 38 62 74 80

рис. 1. Сортировка массива методом вставок

Вначале упорядоченная последовательность состоит из первого элемента 38. Рассматриваем элемент 12 — первый из неупорядоченной последовательности. Он меньше 38, поэтому ставится на его место, а 38 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 12, 38.

Рассматриваем первый элемент неупорядоченной последовательности — 80. Он больше всех элементов упорядоченной последовательности и остается на своем месте.

На третьем этапе упорядоченная последовательность состоит из 12, 38, 80, рассматриваемый элемент 15. Место, куда перемещается рассматриваемый элемент, указано стрелкой, элементы упорядоченной последовательности, смещаемые вправо, подчеркнуты.

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

Иными словами, алгоритм сортировки массива методом вставок выглядит следующим образом:

нц для i от 2 до n

| Разместить элемент a[i] на соответствующем ему

| месте в предшествующей последовательности

кц

Размещение элемента массива на соответствующем ему месте в предшествующей, уже упорядоченной последовательности может быть проведено двумя способами.

1. Можно последовательно сравнивать рассматриваемый элемент с элементом, расположенным слева от него, и обменивать их местами до тех пор, пока слева от перемещаемого элемента не окажется элемент, меньший или равный ему. Такой способ будем называть "сравнение и обмен". Поскольку k-й элемент как бы «проникает на положенный для него уровень», то процесс поиска требуемой позиции часто называют «просеиванием».

2. Можно также сначала определить место, соответствующее рассматриваемому элементу в упорядоченной последовательности, а затем разместить его в этой ячейке, сместив соответствующие элементы на одну позицию вправо, как это показано на рис. 1. Эту разновидность размещения назовем "поиск места и вставка".

Рассмотрим процедуры, соответствующие этим вариантам.