Простейшая карманная сортировка.

Как было отмечено ранее, специальные методы сортировки основаны либо на использовании некоторой дополнительной информации об исходном наборе данных, либо на использовании дополнительной памяти, сопоставимой по объему с самим сортируемым массивом. Отсюда следует, что они имеют ограниченную область применения, но их огромное преимущество – более высокая эффективность, оцениваемая как O(n).

Самая простая разновидность специальных методов – так называемая карманная сортировка.

Пусть как обычно исходный набор данных включает n элементов, причем относительно их ключей известно следующее:

· ключи являются целыми числами, изменяющимися только от 1 до n

· все эти ключи различные

В этом случае ключи можно рассматривать как индексы элементов в массиве. Если в исходном массиве значение ключа может НЕ совпадать с индексом элемента, то после сортировки соответствие должно быть полным: ключ 1 – в ячейке 1, ключ 2 - в ячейке 2 и т.д., ключ n – в ячейке n.

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

Например, для массива из 10 элементов с неповторяющимися ключами от 1 до 10 получим:

Вся сортировка сводится лишь к 10 пересылкам и не требует ни одного сравнения! Реализация - одним единственным циклом (здесь Mas – исходный массив, RezMas - результирующий):

fori := 1 to n do

RezMas[Mas[i].key] := Mas[i];

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

· берем первый элемент в исходном массиве, пусть его ключ равен i

· перемещаем в массиве первый элемент в ячейку i, а i-ый элемент – в первую ячейку; после этой операции i-ый элемент окажется на своем месте

· если ключ первого элемента не равен 1 (например – j ), то обмениваем его с j-ым элементом, после чего и j-ый элемент оказывается на своем месте

· повторяем эти действия до тех пор, пока на первом месте не окажется элемент с ключом 1, причем каждое повторение обязательно размещает один элемент массива на своем “законном” месте

· при необходимости повторяем эти действия и для других элементов массива

Пример работы алгоритма – в следующей таблице.

В этом примере потребовалось 17 сравнений и 7 пересылок. В общем случае, трудоемкость метода пропорциональна n.

Схема программной реализации:

for i := 1 to n do

while Mas[i]. key <> i do

“переставить Mas[i] и Mas[Mas[i].key]”;