Улучшение классических методов сортировки
Нахождение медианы
Медиана – элемент последовательности, значение которого не больше значений одной половины этой последовательности. Например, медианой последовательности чисел 38 7 5 90 65 8 74 43 2 является 38.
Соответствующая отсортированная последовательность будет выглядеть так: 2 5 7 8 38 43 65 74 90.
Задачу нахождения медианы можно решить просто – предварительно отсортировать исходный массив и выбрать средний элемент. Но К. Хоор предлагает метод, который решает задачу нахождения медианы быстрее и соответственно может рассматриваться как вспомогательный для реализации других задач. Достоинство метода К. Хоора заключается в том, что с его помощью можно эффективно находить не только медиану, но и значение k-го по величине элемента последовательности. Например, третьим по величине элементом приведенной выше последовательности будет 7.
Значение k-го элемента массива определяется по формуле k=n/2, где n – длина исходной последовательности чисел.
Ниже приведена программа prg4_123.asm, которая находит элемент-медиану массива. Аналогичную функцию выполняет и процедура median, но процедура отличается тем, что ее можно вызывать динамически во время работы программы, в которой она используется.
ПРОГРАММА prg4_123 // //prg4_123 – программа на псевдоязыке нахождения k-го по величине элемента массива mas длиною п. ;Для нахождения медианы к=п/2. //Вход: mas[n] – неупорядоченная последовательность двоичных значений : к – номер искомого по величине элемента mas[n]. //Выход: х – значение к-го по величине элемента последовательности mas[n]. //….. ПЕРЕМЕННЫЕ INT_BYTE n:;длина mas[n] INT_BYTE mas[n]: //сортируемый массив размерностью n (О..n-l) INTJYTE X:W;i=0: j=0; 1=0; г=0 // j: 1; г – индексы НАЧПРОГ 1: = 1: г: = п ПОКА 1<г ДЕЛАТЬ НАЧ_БЛОК_1 х: = а[к]: 1: = 1: j: = r ПОВТОРИТЬ ПОКА a[i]<x ДЕЛАТЬ i: = i+l ПОКА х< a[j] ДЕЛАТЬ j: = j-l ЕСЛИ i<j TO НАЧ_БЛ0К_2 w: = a[i]: а[1]:-аШ; a[j]: = w i: = i+l: j: = j-l К0Н_БЛ0К_2 ПОКА (i>j) ЕСЛИ j<k TO 1: = I ЕСЛИ k<i T0 r: = j КОН_БЛОК_1 КОН_ПРОГ ;prg4_123 – программа на ассемблере нахождения k-го по величине элемента массива mas длиною п. Для нахождения медианы к=п/2. .data jge $+6 movR.di:R<-J:цикл(1)конец jmp @@m8
Быстрая сортировка
Последний рассматриваемый нами алгоритм (программа prglO_223.asm) является улучшенным вариантом сортировки прямым обменом. Этот метод разработан К. Хоором в 1962 году и назван им "быстрой сортировкой". Эффективность быстрой сортировки зависит от степени упорядоченности исходного массива. Для сильно неупорядоченных массивов – это один из лучших методов сортировки. В худшем случае, когда исходный массив почти упорядочен, его быстрая сортировка по эффективности не намного лучше сортировки прямым обменом.
Идея метода быстрой сортировки состоит в следующем. Первоначально среди элементов сортируемого массива mas[l..n] выбирается один mas[k], относительно которого выполняется переупорядочивание остальных элементов по принципу – элементы mas[i]<mas[k] (i=0..n-1) помещаются в левую часть mas; элементы mas[i]>mas[k] (i=0..n-1) помещаются в правую часть mas. Далее процедура повторяется в полученных левой и правой подпоследовательностях и т. д. В конечном итоге исходный массив будет правильно отсортирован.
В идеальном случае элемент mas[k] должен являться медианой последовательности, то есть элементом последовательности, значение которого не больше значений одной части и не меньше значений оставшейся части этой последовательности. Нахождению медианы было посвящено обсуждение программ предыдущего раздела. В следующей программе элементом mas[k] является самый левый элемент подпоследовательности.