Remkomplekty.ru

IT Новости из мира ПК
6 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Быстрая сортировка матрицы паскаль

Урок 39. Метод быстрой сортировки с разделением

Урок из серии: «Программирование на Visual Basic для школьников»

В предыдущем уроке рассказывалось о сортировке числового массива методом «пузырька».

Оба выше рассмотренных метода просты и наглядны, но не эффективны. Значительно быстрее работает алгоритм сортировки Хоара, который называют сортировкой с разделением или «быстрой сортировкой».

Сортировка методом простого обмена требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы.

Можно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнении и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Хоар в 1962 году. Поскольку производительность этого метода просто впечатляюща, автор назвал его «быстрой сортировкой».

Идея метода

1. В исходном неотсортированном массиве выбрать некоторый элемент x = a(k) (барьерный элемент).

2. Переставить элементы массива таким образом, чтобы слева от x оказались элементы массива, меньшие или равные x, а справа ­ элементы массива, большие чем х.

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

Рассмотрим применение метода «быстрой сортировки» на примере.

Исходный массив состоит из 5 элементов:

Разделение:

1. Выбрать средний элемент массива (x = 67)

2. Установить L = 1, R=n.

3. Увеличивая L, найти первый элемент a(L), который >= x (который должен стоять справа)

4. Уменьшая R, найти первый элемент a(R), который R, разделение закончено.

Для данного массива сортировка по возрастанию методом быстрой сортировки с разделением выполняется за 5 итераций.

Проект «Быстрая сортировка»

Ход выполнения проекта

  1. Создадим графический интерфейс проекта. Поместим на форму:
    • список ListBox1 для вывода значений исходного массива;
    • список ListBox2 для вывода отсортированного массива;
    • кнопку Button1 для заполнения массива с клавиатуры.
    • кнопку Button2 для запуска сортировки.


Объявим переменные для использования в программном модуле

Напишем программный код процедуры быстрой сортировки:

Щелкните по кнопке Сортировать массив. Во второй список будет выведен отсортированный массив, в поле надписи — количество итераций.

В этом уроке мы рассмотрели один из самых быстрых методов сортировки — сортировку с разделением или сортировку Хоара.

На этом мы заканчиваем изучение алгоритмов сортировки числовых массивов.

Быстрая сортировка.

Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.

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

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

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

  • разбиение массива относительно опорного элемента;
  • рекурсивная сортировка каждой части массива.

Разбиение массива.

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

В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):

  1. вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;
  2. вычисляется значение опорного элемента (first+last)/2, и заноситься в переменную mid;
  3. указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas[first]>mid. А указатель last смещается от конца массива к его началу, пока Mas[last] mid, следовательно firstостается равным 1. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 8 и значением 8. Mas[8]>mid, следовательно last смещается на одну позицию влево. Mas[7] mid, следовательно first остается равным 2. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 6 и значением 1: Mas[6] mid, следовательно last смещается на одну позицию влево. Теперь first=last=4, а значит, условие first 1», нужно действовать примерно по следующей схеме:

Имеется массив Mas[L..R], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L

Быстрая сортировка матрицы паскаль

Быстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

  • разбиение массива относительно опорного элемента;
  • рекурсивная сортировка каждой части массива.

O(n log n) (обычное разделение)
или O(n) (разделение на 3 части)

O(n) вспомогательных
O(log n) вспомогательных

Реализация алгоритма на различных языках программирования:

Работает для произвольного массива из n целых чисел.

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

Java/C#

C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable

C# с использованием лямбда-выражений

Быстрая сортировка на основе библиотеки STL.

Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)

JavaScript

Python

С использованием генераторов:

Haskell

Математическая версия — с использованием генераторов:

Common Lisp

В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является «честной» — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, «на том же месте». При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует «императивные» макросы Common Lisp’а.

Pascal

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

Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.

Устойчивый вариант (требует дополнительно O(n)памяти)

Быстрая сортировка, нерекурсивный вариант

Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных.

TURBO PASCAL

Цель: изучение алгоритма быстрой сортировки и ее модификаций.

На этом занятии мы изучим алгоритм быстрой сортировки, который, пожалуй, используется более часто, чем любой другой. Основа алгоритма была разработана в 1960 году (C.A.R.Hoare) и с тех пор внимательно изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы.

Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень «хрупок»: небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.

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

Улучшить алгоритм быстрой сортировки является большим искушением: более быстрый алгоритм сортировки — это своеобразная «мышеловка» для программистов. Почти с того момента, как Oia?a впервые опубликовал свой алгоритм, в литературе стали появляться «улучшенные» версии этого алгоритма. Было опробовано и проанализировано множество идей, но все равно очень просто обмануться, поскольку алгоритм настолько хорошо сбалансирован, что результатом улучшения в одной его части может стать более сильное ухудшение в другой его части. Мы изучим в некоторых деталях три модификации этого алгоритма, которые дают ему существенное улучшение.

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

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

program Quitsort;
uses
crt;
Const
N=10;
Type
Mas=array[1..n] of integer;
var
a: mas;
k: integer;
function Part(l, r: integer):integer;
var
v, i, j, b: integer;
begin
V:=a[r];
I:=l-1;
j:=r;
repeat
repeat
dec(j)
until (a[j] =v) or (i=j- 1);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
a[j]:=a[i];
a[i]:= a[r];
a[r]:=b;
part:=i;
end;
procedure QuickSort(l, t: integer);
var i: integer;
begin
if l

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

Самая сомнительная черта вышеприведенной программы состоит в том, что она очень мало эффективна на простых подфайлах. Например, если файл уже сортирован, то разделы будут вырожденными, и программа просто вызовет сама себя N раз, каждый раз с меньшим на один элемент подфайлом. Это означает, что не только производительность программы упадет примерно до N 2 /2, но и пространство необходимое для ее работы будет около N (смотри ниже), что неприемлемо. К счастью, есть довольно простые способы сделать так, чтобы такой «худший» случай не произошел при практическом использовании программы.

Когда в файле присутствуют одинаковые ключи, то возникает еще два сомнительных вопроса. Первое, должны ли оба указателя останавливаться на ключах равных делящему элементу или останавливать только один из них, а второй будет проходить их все, или оба указателя должны проходить над ними. На самом деле, этот вопрос детально изучался, и результаты показали, что самое лучшее — это останавливать оба указателя. Это позволяет удерживать более или менее сбалансированные разделы в присутствии многих одинаковых ключей. На самом деле, эта программа может быть слегка улучшена терминированием сканирования j l then» на вызов сортировки вставкой (соответственно измененной для восприятия границ сортируемого подфайла): «if r-l m then
begin
i:=part (l,t);
QuickSort (l,i-1);
QuickSort (i+1,t);
end
Else
Insert(l,t);
end;

2. Деление по Медиане из Трех

Второе улучшение в алгоритме быстрой сортировки состоит в попытке использования лучшего делящего элемента. У нас есть несколько возможностей. Наиболее безопасная из них будет попытка избежать худшего случая посредством выбора произвольного элемента массива в качестве делящего элемента. Тогда вероятность худшего случая становится пренебрежимо мала. Это простой пример «вероятностного» алгоритма, который почти всегда работает вне зависимости от входных данных. Произвольность может быть хорошим инструментом при разработке алгоритмов, особенно если возможны подозрительные входные данные.

Более полезное улучшение состоит в том, чтобы взять из файла три элемента, и затем использовать среднее из них в качестве делящего элемента. Если элементы взяты из начала, середины, и конца файла, то можно избежать использования сторожевых элементов: сортируем взятые три элемента, затем обмениваем центральный элемент с a[r-1], и затем используем алгоритм деления на массиве a[l+1..r-2]. Это улучшение называется делением по медиане из трех.

Метод деления по медиане из трех полезен по трем причинам. Во-первых, он делает вероятность худшего случая гораздо более низкой. Чтобы этот алгоритм использовал время пропорциональной N2, два из трех взятых элементов должны быть либо самыми меньшими, либо самыми большими, и это должно повторяться из раздела в раздел. Во-вторых, этот метод уничтожает необходимость в сторожевых элементах, поскольку эту роль играет один из трех взятых нами перед делением элементов. В третьих, он на самом деле снижает время работы алгоритма приблизительно на 5%.

procedure exchange(i,j:integer);
var
k:integer;
begin
k:=a[i];
a[i]:=a[j];
a[j]:=k;
end;

procedure Mediana;
var i:integer;
begin
i:=n div 4;<Рис.>
if a[i]>a[i*2] then
if a[i]>a[i*3] then
exchange(i,n)
else
exchange(i*3,n)
else
if a[i*2]>a[i*3] then
exchange(i*2,n);
quicksort(1,n);
end;

3. Нерекурсивная реализация.

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

Комбинация нерекурсивной реализации деления по медиане из трех с отсечением на небольшие файлы может улучшить время работы алгоритма от 25% до 30%.

Итак, на сегодняшнем занятии мы рассмотрели алгоритм быстрой сортировки.

Быстрая сортировка матрицы паскаль

«Быстрая сортировка», хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе «разделяй-и-властвуй». Общая схема такова:

  1. из массива выбирается некоторый опорный элемент a[i],
  2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] — вправо,
  3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,
  4. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.

На входе массив a[0]. a[N] и опорный элемент p, по которому будет производиться разделение.

  1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
  2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] 2 ) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге. Вообще говоря, малореальная ситуация.

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

Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.

Модификации кода и метода

Из-за рекурсии и других «накладных расходов» Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%.

Для проведения метода в жизнь можно модифицировать функцию quickSortR, заменив последние 2 строки на

Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из -50 , так что интерес скорее теоретический, нежели практический. Однако, поведение «быстрой сортировки» является «эталоном» для аналогично реализованных алгоритмов типа «разделяй-и-властвуй». Не везде можно свести вероятность худшего случая практически к нулю, поэтому такая ситуация заслуживает изучения.

Пусть, для определенности, каждый раз выбирается наименьший элемент amin . Тогда процедура разделения переместит этот элемент в начало массива и на следующий уровень рекурсии отправятся две части: одна из единственного элемента amin, другая содержит остальные n-1 элемента массива. Затем процесс повторится для части из (n-1) элементов.. И так далее..
При использовании рекурсивного кода, подобного написанному выше, это будет означать n вложенных рекурсивных вызовов функции quickSort.
Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям.

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

Псевдокод.
Реализация на Си.

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Читать еще:  Неизвестное имя паскаль
Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×