Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Быстрая сортировка (Хоара)




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

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

На каждом шаге метода мы сначала выбираем «средний» элемент, затем переставляем элементы массива так, что он делится на три части: сначала следуют элементы, меньшие «среднего», потом равные ему, а в третьей части - большие. После такого деления массива остается только отсортировать первую и третью его части, с которыми мы поступим аналогично (разделим на три части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован.

Запишем то, что мы сейчас сформулировали:

procedure Sort;procedure QuickSort(a, b: Longint);Var x: Longint; {индекс «среднего» элемента}begin x := элемент_выбранный_средним; ...деление на три части: 1) A[a]..A[i]; 2) A[i+1]..A[j-1]; 3) A[j]..A[b] if i>a then QuickSort(a, i); if b>j then QuickSort(j, b);end;begin Sort(1, N);end;

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

i := A[l]; y := A[(l+r)div 2]; j := A[r];if i<=y then if y<=j then x := (l+r)div 2 else if i<=j then x := r else x := lelse if y>=j then x := (l+r)div 2 else if i>=j then x := r else x := l;

Теперь нам надо разделить массив относительно элемента A[x] так, чтобы сначала следовали элементы, меньшие A[x], затем сам элемент A[x], а потом уже элементы, большие или равные A[x]. Для этого мы, двигаясь слева найдем первый элемент A[i], больший A[x], и, двигаясь справа, - первый элемент A[j], меньший A[x]. Если i окажется меньше j, то это значит, что массив еще не поделен на три искомых части, в таком случае обменяем местами элементы A[i] и A[j], а затем продолжим поиск слева от A[i] и справа от A[j].

i := l; j := r; x := A[x];repeat while A[i] < x do Inc(I); while x < A[j] do Dec(j); if i <= j then begin y := A[i]; A[i] := A[j]; A[j] := y; Inc(i); Dec(j); end;until i > j;

Пойдем дальше. Заметим, что все-таки наш способ нахождения «среднего» элемента подмассива в худшем случае приведет к тому, что после деления, например, правая и средняя части поделенного массива будут содержать по одному элементу, а левая все остальные. В этом случае, если мы сначала вызовем QuickSort для левой части, то (опять же в худшем случае) это может породить порядка N рекурсивных вызовов. А значит нам надо будет завести дополнительную память размером пропорциональным N и пространственная сложность будет O(N). Этого можно избежать, если сначала вызывать QuickSort для меньшей части. Тогда можно гарантировать пространственную сложность O(log(N)).



Теперь осталось только собрать вместе части программы:

procedure Sort;procedure QuickSort(a, b: Longint);Var x: Longint; {индекс «среднего» элемента}begin i := A[l]; y := A[(l+r)div 2]; j := A[r]; if i<=y then if y<=j then x := (l+r)div 2 else if i<=j then x := r else x := l else if y>=j then x := (l+r)div 2 else if i>=j then x := r else x := l; i := l; j := r; x := A[x]; repeat while A[i] < x do Inc(i); while x < A[j] do Dec(j); if i <= j then begin y := A[i]; A[i] := A[j]; A[j] := y; Inc(i); Dec(j); end; until i > j; if l-j<i-r then begin if l < j then QuickSort(l, j); if i < r then QuickSort(i, r); end else begin if i < r then Sort(i, r); if l < j then Sort(l, j); end; end;begin QuickSort(1, N);end;

В худшем случае этот алгоритм дает временную сложность Tmax(N2) (для случая, когда все выборки «среднего» элемента оказались неудачны), но как показывают теоретические исследования вероятность такого случая очень мала. В среднем же и в лучшем случае получим T(N*log(N)).


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал