Сортировка простым выбором

Сортировка бинарными вставками

Сортировку простыми вставками можно немного улучшить: поиск "подходящего места" в упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный поиск в упорядоченной последовательности. После каждого сравнения обрабатываемая последовательность сокращается в два раза. Пусть, к примеру, нужно найти место для элемента 7 в таком массиве: [2 4 6 8 10 12 14 16 18] Найдем средний элемент этой последовательности (10) и сравним с ним семерку. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения: [2 4 6 8] 10 12 14 16 18

Снова возьмем середину в отмеченном куске последовательности, чтобы сравнить ее с семеркой. Однако точной середины у новой последовательности нет, поэтому нужно решить, который из двух центральных элементов станет этой "серединой". От того, к какому краю будет смещаться выбор в таких случаях, зависит окончательная реализация нашего алгоритма. Договоримся, что "серединой" последовательности всегда будет становиться левый центральный элемент. Это соответствует вычислению номера "середины" по формуле nomer_sred:= (nomer_lev + nomer_prav)div 2

Итак, отсечем половину последовательности: 2 4 [6 8] 10 12 14 16 18

И снова: 2 4 6 [8] 10 12 14 16 18 2 4 6][8 10 12 14 16 18

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

[2 4 6 8] 10 12 14 16 18 2 4 [6 8] 10 12 14 16 18 2 4 6 [8] 10 12 14 16 18 2 4 6 8][10 12 14 16 18

Из приведенных примеров уже видно, что поиск ведется до тех пор, пока левая граница не окажется правее(!) правой границы. Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг "хвоста" последовательности.

Реализация алгоритма БинВст

for i:= 2 to n do

if a[i-1]>a[i] then

begin x:= a[i];

left:= 1;

right:= i-1;

repeat

sred:= (left+right)div 2;

if a[sred]<x then left:= sred+1

else right:= sred-1;

until left>right;

for j:= i-1 downto left do a[j+1]:= a[j];

a[left]:= x;

end;

Эффективность алгоритма БинВст ~N2.

Алгоритм ПрВыб

На каждом шаге (всего их будет ровно N-1) будем производить такие действия:

1. найдем минимум среди всех еще не упорядоченных элементов;

2. поменяем его местами с первым "по очереди" не отсортированным элементом.

Реализация ПрВыб

for i:= 1 to n-1 do

begin min_ind:= i;

for j:= i+1 to n do

if a[j]<=a[min_ind] {***}

then min_ind:= j;

if min_ind<>i

then begin

x:= a[i];

a[i]:= a[min_ind];

a[min_ind]:= x;

end; end;

Эффективность алгоритма ПрВыб ~N2

Пример сортировки

Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками: 5 3 4 3 6 2 1

Теперь мы будем придерживаться алгоритма ПрВыб (подчеркнута несортированная часть массива, а квадратиком выделен ее минимальный элемент):

1 шаг: 5343621

2 шаг: 1343625

3 шаг: 1 243635 {***}

4 шаг: 12 33645 {ничего не делаем}

5 шаг: 123 3645 6 шаг: 1233 465

результат: 12334 56

Дата добавления: 2014-01-20