![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Быстрая сортировка (Хоара)
Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым методом сортировки из тех, что оперируют сравнениями. Этот метод является ярким примером реализации принципа «разделяй и властвуй». Как показывают теоретические выкладки наиболее эффективным в общем случае оказывается разделение задачи на две равные по сложности части, что мы и будем пытаться делать в этом методе. На каждом шаге метода мы сначала выбираем «средний» элемент, затем переставляем элементы массива так, что он делится на три части: сначала следуют элементы, меньшие «среднего», потом равные ему, а в третьей части - большие. После такого деления массива остается только отсортировать первую и третью его части, с которыми мы поступим аналогично (разделим на три части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован. Запишем то, что мы сейчас сформулировали: 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]. Пойдем дальше. Заметим, что все-таки наш способ нахождения «среднего» элемента подмассива в худшем случае приведет к тому, что после деления, например, правая и средняя части поделенного массива будут содержать по одному элементу, а левая все остальные. В этом случае, если мы сначала вызовем 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)).
|