Студопедия

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

КАТЕГОРИИ:

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






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






{быстрая сортировка} procedure QuickSort(var item: DataArray; count: integer); procedure qs(l, r: integer; var it: DataArray); var i, j: integer; x, y: DataItem; begin i: =l; j: =r; x: =it[(l+r) div 2]; repeat while it[i]< x do i: = i+1; while x< it[j] do j: = j-1; if y< =j then begin y: = it[i]; it[i]: = it[j]; it[j]: = y; i: = i+1; j: = j-1; end; until i> j; if l< j then qs(l, j, it); if l< r then qs(i, r, it) end; begin qs(1, count, item); end; type DataItem = string[80]; DataArray = array [1..80] of DataItem; {алгоритм быстрой сортировки для символьных строк } procedure QsString(var item: DataArray; count: integer); procedure qs(l, r: integer; var it: DataArray); var i, l: integer; x, y: DataItem; begin i: = l; j: = r; x: = it[(l+r) div 2]; repeat while it[i] < x do i: = i+1; while x < it[j] do j: = j-1; if i< =j then begin y: = it[i]; it[i]: = it[j]; it[j]: = y; i: = i+1; j: = j-1; end; until i> j; if l< j then qs(l, j, it); if l< r then qs(i, r, it); end; begin qs(1, count, item); end; {быстрая сортировка записей с почтовым адресом} procedure QsRecord(var item: DataArray; count: integer); procedure qs(l, r: integer; var it: DataArray); var i, j: integer; x, y: DataItem; begin i: = l; j: = r; x: = it[(l+r) div 2]; repeat while it[i].name < x.name do i: = i+1; while x.name < it[j].name do j: = j-1; if i< =j then begin y: = it[i]; it[i]: = it[j]; it[j]: = y; i: = i+1; j: = j-1; end; until i> j; if l< j then qs(l, j, it); if l< r then qs(i, r, it) end; begin qs(1, count, item); end;

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

Сортировка подфайлов, содержащих меньше чем М элементов, выполняется каким-либо простым методом, например простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части. Блок выбора Х в простейшем случае формулируется как X=K[l], однако это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение - выбирать Х как случайный ключ из диапазона K[l]... K[r] и обменять его с K[l].


Поделиться с друзьями:

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