Алгоритмы и структуры данных. Сортировка массива методом прямого включения Сортировка методом прямого включения c

Необходимые определения и классификация сортировок.

Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность

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

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

Эффективность сортировки можно рассматривать с нескольких критериев:

1) время, затрачиваемое на сортировку;

2) объем оперативной памяти, требуемой для сортировки;

3) время, затраченное программистом на написание программы.

Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов.

Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn) до о(n 2) , где о(n) - идеальный и недостижимый случай.

Методы сортировки можно классифицировать примерно так:

1) строгие (прямые) методы (их эффективность примерно одинакова):

· прямого включения ;

· прямого выбора ;

· прямого обмена ;

2) улучшенные методы .

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

Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i- й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности.

Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию.

Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом.

Таблица 11.1

Принцип работы сортировки прямым включением

Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов.

Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).

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

Сортировка этим методом производится последовательно шаг за шагом. На k –м шаге считается, что часть массива, содержащая первые k– 1 элемент, уже упорядочена, то есть .

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

С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n– 1 шаг.

Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента х . Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы а(j) , j изменяется от k– l до 1. Такой просмотр закончится при выполнении одного из следующих условий:

Найден элемент , что говорит о необходимости вставки х между и а(j) .

Достигнут левый конец упорядоченной части массива, следовательно, нужно вставить х на первое место.

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

Методику сортировки иллюстрирует таблица 2:

Таблица 2 – Пример сортировки с помощью прямого включения

Первоначально упорядоченная последовательность состоит из 1–го элемента 9. Элемент а(2) =5 – первый из неупорядоченной последовательности и 5 < 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент а(3) =15 неупорядоченной последовательности больше всех элементов упорядоченной последовательности, поэтому остаётся на своём месте и на следующем шаге упорядоченная последовательность состоит из 5, 9, 15, а рассматриваемый элемент 6. Процесс происходит до тех пор, пока последовательность не станет упорядоченной.

Шейкерная сортировка

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

На этих наблюдениях основан метод шейкерной сортировки (ShakerSort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге "всплывает" очередной наиболее легкий элемент, а на другом "тонет" очередной самый тяжелый. Пример шейкерной сортировки приведен в таблице 3.

Таблица 3 – Пример шейкерной сортировки

Сортировка массива с помощью включений с уменьшающимися расстояниями (метод Шелла)

Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения.

Идея метода: все элементы массива разбиваются на группы таким образом, что в каждую группу входят элементы, отстоящие друг от друга на некоторое число позиций L . Элементы каждой группы сортируются. После этого все элементы вновь объединяются и сортируются в группах, при этом расстояние между элементами уменьшается. Процесс заканчивается после того, как будет проведено упорядочивание элементов с расстоянием между ними, равным 1.

Пример сортировки методом Шелла приведен в таблице 4.

Таблица 4 – Пример сортировки методом Шелла

Сначала рассмотрим вариант, когда первоначальное значение L равно половине числа элементов в массиве, а каждое последующее значение вдвое меньше предыдущего. Заметим, что обмениваются элементы, которые отстоят на величину шага. Если при сравнении 2–х элементов обмена не произошло, то места сравниваемых элементов сдвигаются вправо на одну позицию. Если обмен произошёл, то происходит сдвиг соответствующих сравниваемых элементов на L .

Сортировка разделением (быстрая сортировка)

Метод сортировки разделением был предложен Чарльзом Хоаром. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть методом быстрой сортировки – «Quicksort».

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x , после чего массив просматривается слева, пока не встретится элемент a(i) такой, что a(i) > x , а затем массив просматривается справа, пока не встретится элемент a(i) такой, что a(i) < x . Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x . В результате массив окажется разбитым на две части – левую, в которой значения ключей будут меньше x , и правую со значениями ключей, большими x . Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива.

Процесс сортировки массива быстрым методом представлен в таблице 5.

Таблица 5 – Пример быстрой сортировки

Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже “готовую” последовательность A1 … An и исходную последовательность Ai … An. При каждом шаге, начиная с i=2 и увеличивая I каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется в нужное место.

Выше показан в качестве примера процесс сортировки с помощью включения восьми случайно выбранных чисел:Алгоритм этой сортировки таков:

FOR i:=2 ТО n DО

включение х на соответствующее место среди а ... a[j];

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

1. Найден элемент aj с ключом, меньшим чем ключ у Х.

2. Достигнут левый конец готовой последовательности.

Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом барьера (sentinel). Здесь его легко применить, поставив барьер a0 со значением Х. (Заметим, что для этого необходимо расширить диапазон индекса в описании переменной а до 0 ... n.)

Анализ метода.прямого включения. Число сравнений ключей (Ci) при i-ом просеивании самое большее равно i - 1,самое меньшее – 1; если предположить, что все перестановки из п ключей равновероятны, то среднее число сравнений - i/2. Число, же пересылок (присваиваний элементов) Mi равно Ci + 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:

Сave = (n2 + n - 2)/4,

Сmax = (n2 + n - 4)/4,

М min = З*(n - 1),

М ave = (n2 + 9n - 10)/4,

М max = (n2 + 3n - 4)/2.

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

Алгоритм с прямыми включениями можно легко улучшить, если обратить внимание на то, что готовая последовательность (a1 … ai-1 , в которую надо вставить новый элемент, сама уже упорядочена. Естественно остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением (binary insertion).

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

При обработке данных важно знать информационное поле данных и размещение их в машине.

Различают внутреннюю и внешнюю сортировку:

Внутренняя сортировка - сортировка в оперативной памяти;

Внешняя сортировка - сортировка во внешней памяти.

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

При сортировке могут встретиться одинаковые ключи. В этом случае желательно после сортировки расположить одинаковые ключи в том же порядке, что и в исходном файле. Это - устойчивая сортировка .

Мы будем рассматривать только сортировки, не использующие дополнительную оперативную память. Такие сортировки называются «на том же месте» .

Эффективность сортировки можно рассматривать по нескольким критериям:

Время, затрачиваемое на сортировку;

Объем оперативной памяти, требуемой для сортировки;

Время, затраченное программистом на написание программы.

Выделяем первый критерий. Эквивалентом затраченного на сортировку времени можно считать количество сравнений и количество перемещений при выполнении сортировки.

Порядок числа сравнений и перемещений при сортировке лежит в пределах

От О (n log n) до О (n 2);

О (n) - идеальный и недостижимый случай.

Различают следующие методы сортировки:

Строгие (прямые) методы;

Улучшенные методы.

Строгие методы:

Метод прямого включения;

Метод прямого выбора;

Метод прямого обмена.

Эффективность строгих методов примерно одинакова.

Сортировка методом прямого включения

Элементы мысленно делятся на уже готовую последовательность a 1 ,...,a i-1 и исходную последовательность.

При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Суть алгоритма такова:

for i = 2 to n

X = a(i)

Находим место среди а(1)…а(i) для включения х

next i

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

Алгоритм сортировки методом прямого включения без барьера

for i = 2 to n

X = a(i)

For j = i - 1 downto 1

If x < a(j)

Then a(j + 1) = a(j)

Else go to L

Endif

Next j

L: a(j + 1) = x

next i

return

Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while , то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.

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

for i = 2 to n

X = a(i)

A(0) = x {a(0) - барьер}

J = i - 1

While x < a(j) do

A(j +1) = a(j)

J = j - 1

Endwhile

A(j +1) = x

next i

return

Эффективность алгоритма прямого включения

Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С max = n(n - 1)/2, т. е. - О (n 2). Количество перестановок M max = C max + 3(n-1), т.е. - О (n 2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: C min = n-1; M min = =3(n-1).

Сортировка с помощью прямого обмена (пузырьковая сортировка)

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

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

C min = n - 1, порядок О(n),

а перемещения вообще отсутствуют

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

Такой метод широко известен под именем "пузырьковая сортировка".

Алгоритм метода прямого обмена

for j = n to i step -1

if a(j) < a(j - 1) then

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl , который остается в значении false , если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены жирным шрифтом.

fl = true

if fl = false then return

fl = false

for j = n to i step -1

if a(j) < a(j - 1) then

fl = true

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

Эффективность алгоритма сортировки прямым обменом

Число сравнений C max = n(n-1)/2 , порядок О(n 2).

Число перемещений М max =3C max =3n(n-1)/2, порядок О(n 2).

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

Для сортировки (упорядочения) по возрастанию или убыванию значений в массиве разработано множество методов [Вирт, Кнут. т 3].Рассмотрим три из них, считая, для определённости, что первые n, n=6, элементов массива Х

На каждом следующем i-том шаге, i=2, 3,…,n-1, значение из (i+1)-ой ячейки массива путем обмена положением с числом из предыдущей ячейки продвигают в сторону уменьшения индекса ячейки до тех пор, пока ни окажется, что в предыдущей ячейке находится меньшее число.

Из сказанного следует, что при реализации метода прямого включения внешний цикл должен выполняться n-1 раз, а максимально возможное число выполнений внутреннего цикла, в теле которого должны выполняться сравнения и перестановки чисел, будет увеличиваться от 1 до n-1. Однако внутренний цикл следует организовать так, чтобы он заканчивался или вообще не выполнялся при наступлении условия: значение в предыдущей ячейке массива меньше, чем в текущей.

В нашем примере:

При i=2 число 15 из ячейки Х 3 последовательно обменяется местами с числом 34 из ячейки Х 2 , а затем с числом 21 из ячейки Х 1 ,

При i=4 число 25 из ячейки Х 5 обменяется местами с числом 34 из ячейки Х 3 ,

Ниже представлен фрагмент программы упорядочения по возрастанию первых n элементов массива X методом прямоговключения (включения с сохранением упорядоченности) .

for i:=1 to n-1 do

2. while (X0) do

3. R:=X[j];

   X[j]:=X;

   X:=R;

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

Метод прямого обмена (метод пузырька).

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

На первом шаге последовательно, для j = n, n-1, …,2, сравниваются значения соседних ячеек массива, и при выполнении условия Х j <Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

В нашем примере после выполнения первого шага данные в массиве расположатся так:

На каждом следующем шаге число проверяемых пар ячеек будет уменьшаться на 1. В общем случае, на любом шаге i, i=1, 2, 3, …, n-1, процесс будет выполняться для j от n до i+1, в частности, при i= n-1 – только один раз для n-ой и (n-1)-вой ячеек.

Из сказанного следует, что при реализации метода прямого обмена внешний цикл должен выполняться n-1раз, а число выполнений внутреннего цикла, в теле которого должны выполняться сравнения и перестановки чисел, будет уменьшаться от n-1 до 1.

Происхождение термина “метод пузырька” объясняется так: если представить вертикальное расположение ячеек массива с ростом индекса сверху вниз, то самое маленькое число из рассматриваемых будет подниматься вверх подобно пузырьку в воде.

В нашем примере

При i=3 перестановки приведут к следующему состоянию массива

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

Модифицированный метод прямого обмена (модифицированный метод пузырька).

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

Очевидно, эффект при использовании модифицированного метода пузырька по сравнению с не модифицированным методом в ускорении процесса сортировки будет наблюдаться, если исходная последовательность чисел близка к упорядоченности в нужном направлении. В предельном случае, когда массив уже упорядочен нужным образом тело внешнего цикла будет выполнено только один раз.