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

 

 

МИНОБНАУКИ РФ

 

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФФЕСИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

 

Факультет прикладной математики, информатики и механики

 

Кафедра программного обеспечения и администрирования информационных систем

 

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

Курсовая работа

по специальности 080801 Прикладная информатика в юриспруденции

 

 

Зав. кафедрой____________                             д.ф.-м.н., проф.     Артемов М.А.

Студент_________________                                        2 к. 10 гр.   Мустафаева М.Е

Руководитель____________                                               ст. преп. Вощинская Г.Э М.В.

 

 

Воронеж 2012 

Аннотация

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

 

Введение……………………………………………………………………...4

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

2. Пример реализации быстрой сортировки...............……..…..…………..8

Заключение……………………………………………………….………...10

Литература………………………………...……..…………………..……..11

 

Введение

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

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

 

 

 

 

 

 

 

 

 

 

 

 

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

Быстрая сортировка (quicksort) – широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Алгоритм, основанный на обмене, приводит к самому лучшему из известных на данный момент методу сортировки для массивов. Дает в среднем О(n log n) сравнений при n элементов. В худшем случае, однако, получается О(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой О(n log n), по причине того что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время. В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у  нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но и из этого примера можно извлечь и нечто действительно поучительное.

 Попытаемся воспользоваться  таким алгоритмом: выберем наугад  какой-либо элемент( назовем его  x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент ai>x, затем будем просматривать массив справа, пока не встретим aj<x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x. Теперь этот процесс разделения представим в виде процедуры.

PROCEDURE partition;

VAR w,x: item;

 

BEGIN i:=1; j:=n;

REPEAT

  WHILE a[i]<x DO i:=i+1 END;

  WHILE X<a[j] DO j:=j-1 END;

IF i<=j THEN

  w:=a[i]; a[i]:=a[j]:=w; i:=i+1; j:=j-1

  END

UNTIL i>j

END partion

 Следует обратить внимание, что вместо отношений > и < используются ≤ и ≥, а в заголовке цикла с WHILE – их отрицания < и >. При таких изменениях x выступает в роли барьера для того и другого просмотра. Если взять в качестве x для сравнения средний ключ 42, то в массиве ключей

44 55 12 42 94 06 18 67

Для разделения понадобятся два обмена: 18↔44 и 6↔55

18 06 12 42 94 55 44 67

Последние значения индексов таковы: i=5, а j=3. Ключи a1…ai-1 меньше или равны ключу x=42, а ключи aj+1…an  больше или равны x. Следовательно, существует две части, а именно

Ak:1≤k<i:ak≤x  //2.14

Ak:j<k≤n:x≤ak

Описанный алгоритм очень прост и эффективен, поскольку главные величины i, j и x можно хранить во время просмотра в быстрых регистрах машины. Однако он может оказаться и неудачным, что, например, происходит в случае n идентичных ключей: для разделения нужно n/2 обменов. Этих вовсе необязательных обменов можно избежать, если операторы просмотра заменить на такие:

WHILE a[i]<=x DO i:=i+1 END;

WHILE x<= a[j] DO j:= j-1 END

Однако в этом случае выбранный элемент x, находящийся среди компонент массива, уже не работает как барьер для двух просмотров. В

 

результате просмотры массива со всеми идентичными ключами приведут, если только не использовать более сложные условия их окончания, к переходу через границы массива. Простота условий, употребленных в процедуре partition, вполне оправдывает те дополнительные обмены, которые происходят в среднем относительно редко. Можно еще немного сэкономить, если изменить заголовок, управляющий самим обменом: от i≤ j перейти к i<j. Однако это изменение не должно касаться двух операторов: i:=i+1, j:=j-1. Поэтому для них потребуется отдельный условный оператор. Убедиться в правильности алгоритма разделения можно, удостоверившись, что отношения 2.14 представляют собой инварианты оператора цикла с REPEAT. Вначале при i=1 и j=n их истинность тривиальна, а при выходе C1>j  они дают кА КрАЗ желаемый результат.

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

PROCEDURE Quicksort;

PROCEDURE sort(L,R:index);

  VAR i,j: index; w,x: item;

BEGIN i:=L; j:= R;

x:=a[(L+R) div2];

REPEAT

WHILE a[i]<x DO i:=i+1 END;

WHILE x<a[j] DO j:=j-1 END;

IF i<=j THEN

w:=a[i]; a[i]:=a[j]; a[j]:=w; i:=i+1; j:=j-1

  END

UNTIL i>j;

If L<j THEN sort(L,J) END;

IF i< R THEN sort(I, R) END

END sort;

BEGIN sort(1,n)

END QuickSort

 

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

Суть итеративного решения заключается во введении списка требуемых разделений, т.е разделений, которые необходимо провести. На каждом этапе возникают две задачи по разделению. И только к одной из них можно непосредственно сразу же приступить в очередной итерации, другая же заносится в определенный список. В приводимой нерекурсивной версии Quicksort каждое требование задается просто левым и правым индексами – это границы части, требующей дальнейшего разделения. Таким образом, мы вводим переменную-массив под именем stack и индекс s, указывающий на самую последнюю строку в стеке.

PROCEDURE NonRecursiveQuickSort;

CONST M=12;

VAR I,j,L,R:index; x,w:item;

S:[0..M];

Stack:array[1..M] OF RECORD L,R:index END;

BEGIN s:=1; stack[1].L:=stack[s].R:=n;

 REPEAT //выбор из стека последнего запроса

  L:=stack[s].L; R:=stack[s].R; s;=s-1;

  REPEAT//разделение a[L]..a[R]

    i:=L; j;=R; x;=a[(L+R)DIV2];

  REPEAT

  WHILE a[i]<x DO i:=i+1 END;

  WHILE x<a[j] DO j:=j-1 END;

 IF i<=j THEN

   w:=a[i]; a[i]:=a[j];a[j]:=w; i:=i+1; j:=j-1

   END;

UNTIL i>j;

IF i<R THEN

  s:=s+1; stack[s].L:=I; stack[s].R:=R

END;

  R:=j

   UNTIL L>=R

 UNTIL s=0

END NonRecursiveQuickSort

О том, как выбрать подходящий размер стека M, речь пойдет при анализе работы Quicksort.

Анализ Quicksort. Для исследования производительности Quicksort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение x, проходим целиком по всему массиву. Следовательно, при этом выполняется точно n сравнений. Число же обменов можно определить из следующих соображений. При заданной границе значений x ожидаемое число операций обмена равно числу элементов в левой части разделяемой последовательности, т.е n-1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, если этот элемент перед этим находился в правой части. Вероятность этого равна(n-(x-1))/n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.

M = [Sx:1≤x≤n:(x-1)*(n-(x-1))/n]/n

    = [Su:0≤u≤n-1:u*(n-u)]/n^2

    = n*(n-1)/2n-(2n^2-3n+1)/6n=(n-1/n)/6

В результате общее число сравнений n*log n, а общее число обменов n*log(n)/6. средняя производительность Quicksort при случайном выборе границы отличается от упомянутого оптимального варианта лишь коэффициентом 2*ln(2).

Как бы то ни было, но Quicksort присущи и некоторые недостатки. Главный из них – недостаточно высокая производительность при небольших n, впрочем это недостаток всех усовершенствованных методов. Но пред другими усовершенствованными методами этот имеет то преимущество, что для обработки небольших частей в него можно легко включить какой-либо из прямых методов сортировки.

 

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

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

const max=20; { можно и больше... }

type

  list = array[1..max] of integer;

 

procedure quicksort(var a: list; Lo,Hi: integer);

 

  procedure sort(l,r: integer);

  var

    i,j,x,y: integer;

  begin

    i:=l; j:=r; x:=a[random(r-l+1)+l]; { x := a[(r+l) div 2]; - для выбора среднего элемента }

    repeat

      while a[i]<x do i:=i+1; { a[i] > x  - сортировка по убыванию}

      while x<a[j] do j:=j-1; { x > a[j]  - сортировка по убыванию}

      if i<=j then

      begin

        if a[i] > a[j] then {это условие можно убрать} {a[i] < a[j] при сортировке по убыванию}

        begin

          y:=a[i]; a[i]:=a[j]; a[j]:=y;

        end;

        i:=i+1; j:=j-1;

      end;

    until i>=j;

    if l<j then sort(l,j);

    if i<r then sort(i,r);

  end; {sort}

 

begin {quicksort};

  randomize; {нужно только если используется выборка случайного опорного элемента}

  sort(Lo,Hi)

end; {quicksort}

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

const max=20; { можно и больше… }

type

  list = array[1..max] of integer;

 

procedure quicksort(var a: list; Lo,Hi: integer);

 

  procedure sort(l,r: integer);

  var

    i,j,x,xval,y: integer;

  begin

    i:=l; j:=r; x:=random(r-l+1)+l; xval:=a[x]; xvaln:=num[x]{ x :=(r+l) div 2; - для выбора среднего элемента }

    repeat

      while (a[i]<xval)or((a[i]=xval)and(num[i]<xvaln)) do i:=i+1; {> - сортировка по убыванию}

      while (xval<a[j])or((a[j]=xval)and(xvaln<num[j])) do j:=j-1; {> - сортировка по убыванию}

      if i<=j then

      begin

        y:=a[i]; a[i]:=a[j]; a[j]:=y;

        y:=num[i]; num[i]:=num[j]; num[j]:=y;

        i:=i+1; j:=j-1

      end;

    until i>j;

    if l<j then sort(l,j);

    if i<r then sort(i,r)

  end; {sort}

 

begin {quicksort}

  randomize; {нужно только если используется выборка случайного опорного элемента}

  for i:=1 to n do

    num[i]:=i;

  sort(Lo,Hi)

end; {quicksort}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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