Sadda.ru Ironetcart Андроид Ассемблер MASM32 Linux Все статьи Table of Contents


 

Сортировка расческой

  Макс Петров июнь 2013

      Алгоритм предложен Влодзимежом Добосиевичем (1980), популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine (1991).

      Представляет собой модификацию пузырьковой сортировки, в которой сравнения и перестановки между элементами сортируемого массива происходят с некоторым разрывом (Gap) по длине массива. Будучи максимальным на первом проходе, в каждый последующий проход Gap уменьшается либо арифметически - на некоторую величину (шаг по Gap), либо геометрически - в некоторое число раз (усадочный фактор). По достижении значения Gap = 1 сортировка расческой вырождается в обыкновенную пузырьковую сортировку. Пузырьковая сортировка продолжается, пока массив не будет полностью обработан, т.е. проход пузырьковой сортировки, при котором фиксируется ноль обменов значениями между элементами массива, является последним.

      Считается, что для сортировки расческой с геометрическим уменьшением Gap наилучшим является усадочный фактор, равный 3/4. Значение Gap для k-го прохода вычисляется по простой формуле:
      Gapk = Gapk-1 * 3 / 4
или
      Gapk = Gapk-1 / 4 * 3
то есть значение следующего Gap получают умножением на 3/4 или делением на 4/3 предыдущего значения. С учетом округления именно после деления (так проще) очевидно, что последовательность действий (*3/4 или /4*3) имеет значение, при перемене порядка операций мы получим разные результаты во времени сортировки.

      При программировании на ассемблере требовательного к вычислительным ресурсам алгоритма к геометрическому уменьшению величин можно отнестись с настороженностью, которая будет понятна из соответствующих фрагментов кода (Gap в регистре ECX):

; арифметическое уменьшение Gap (на 100): SUB ECX, 100 ; 2 такта процессора ; геометрическое уменьшение Gap (/4*3) с округлением: MOV EAX, ECX ; 2 такта процессора MOV EDX, 0 ; 2 такта процессора DIV dwDiv4 ; 41 такт процессора (dwDiv4 - dword переменная "4") MOV EDX, 0 ; 2 такта процессора MUL dwMul3 ; 12-21 тактов процессора (dwMul3 - dword переменная "3") MOV ECX, EAX ; 2 такта процессора

      Операции деления и умножения затратны для процессора. Пусть деление на 4 и умножение на 3 и будут производиться во внешнем цикле, очевидно, что часть выгод, которые может сулить геометрическое уменьшение Gap, нивелируется за счет особенностей вычислительных машин.

      Главным недостатком сортировки расческой с геометрическим уменьшением Gap является некоторая вероятность попадания в область неудачных обменов при определенных сочетаниях длины массива и расположения чисел в нем. На графике зависимости скорости сортировки от длины массива такие области проявляются тормозными пиками, где скорость сортировки может быть хуже в десятки раз по сравнению с соседними участками графика. Другими словами, сортировка расческой с геометрическим уменьшением Gap "непредсказуема", и массив меньшего размера может сортироваться этим методом в десятки раз медленнее, по сравнению с сортировкой массива большего размера.

      Алгоритмы (на ассемблере) сортировки расческой с арифметическим и геометрическим уменьшением Gap, также замеры времени сортировок приведены в конце статьи.

      Пример сортировки расческой с арифметическим уменьшением Gap - для первых четырех проходов по массиву из десяти чисел показан на рисунке. Сравнения отмечены стрелками. Начальный разрыв принят равным девяти, шаг, с которым уменьшается разрыв, выбран равным трем.

сортировка расческой

      В первом проходе сравниваются 2 элемента, отстоящие друг от друга на величину Gap = 9:
      первый и десятый.
Так как значение первого элемента больше значения десятого элемента, они обмениваются местами.

      Во втором проходе (Gap = 6) сравниваются элементы:
      первый и седьмой;
      второй и восьмой;
      третий и девятый;
      четвертый и десятый.
Если левый элемент больше правого, происходит обмен.

      В третьем проходе (Gap = 3) сравниваются элементы:
      первый и четвертый;
      второй и пятый;
      третий и шестой;
      четвертый и седьмой;
      пятый и восьмой;
      шестой и девятый;
      седьмой и десятый.
Если левый элемент больше правого, происходит обмен.

      На четвертом проходе Gap = 1 и сортировка расческой превращается в пузырьковую сортировку, последняя продолжится, пока массив не будет отсортирован.

      Очевидно, что эффективность сортировки расческой с арифметическим уменьшением Gap будет зависеть от выбранного шага по Gap, причем, для каждого диапазона длин массивов наилучшим будет свой шаг. В таблице приведены значения времени сортировки для массивов 10 000 - 500 000 элементов при разном шаге. Весьма хорошим является шаг, равный 100.

Таблица. Зависимость продолжительности сортировки расческой от шага по Gap
для периодических массивов одноразрядных десятичных чисел (9, 6, 3, 8, 5, 2, 7, 4, 1, 0...)

шаг по Gap500 000 элементов100 000 элементов10 000 элементов
1022,7 sec0,84 sec0,01 sec
307,86 sec0,33 sec0,01 sec
604,14 sec0,23 sec0,01 sec
1003,17 sec0,22 sec0,01 sec
2002,95 sec0,42 sec0,05 sec
3003,25 sec0,55 sec0,06 sec
4004,31 sec0,91 sec0,08 sec
5003,69 sec0,99 sec0,08 sec
100010,8 sec2,38 sec0,13 sec


;========================================================= ;========================================================= ; СОРТИРОВКА РАСЧЕСКОЙ С АРИФМЕТИЧЕСКИМ УМЕНЬШЕНИЕМ Gap (-100) ; massiv - массив четырехбайтовых чисел; ; massiv_max_index - максимальный индекс массива; ; counter - счетчик обменов, если обменов не было, counter = 0 push massiv_max_index pop ECX ; в ECX - ширина разрыва (Gap) между обменивающимися шариками, ; сначала равна длине массива, затем будет уменьшаться .WHILE 1 ; начало бесконечного цикла mov EDX, 0 ; EDX - индекс для шариков в левой части массива mov EBX, ECX ; EBX - индекс для шариков в правой части массива mov counter, 0 ; обнуляем счетчик обменов .WHILE ebx <= massiv_max_index ; пока индекс справа не дойдет до конца массива mov EAX, massiv[EBX*4] ; засылаем в EAX значение правого элемента .IF massiv[EDX*4] > EAX ; если значение левого элемента больше, чем EAX push EAX ; тогда совершаем обмен через стек push massiv[EDX*4] pop massiv[EBX*4] pop massiv[EDX*4] inc counter ; увеличиваем счетчик обменов .ENDIF inc EBX ; увеличиваем индекс правых inc EDX ; увеличиваем индекс левых .ENDW .IF counter == 0 && ECX == 1 ; проверяем, не пора ли прекратить работу .break .ENDIF .IF ECX > 3000000000 ; если Gap "вылетел" в отрицательные числа mov ECX, 1 ; тогда Gap := 1 (пузырьковая сортировка) .ELSEIF sub ECX, 100 ; иначе Gap := Gap - 100 .ENDIF .ENDW ; возврат на начало бесконечного цикла ;========================================================= ;========================================================= ; СОРТИРОВКА РАСЧЕСКОЙ С ГЕОМЕТРИЧЕСКИМ УМЕНЬШЕНИЕМ Gap (/4*3) ; massiv - массив четырехбайтовых чисел; ; massiv_max_index - максимальный индекс массива; ; counter - счетчик обменов, если обменов не было, counter = 0 ; должны быть объявлены переменные: dwDiv4 dword 4 ; dwMul3 dword 3 push massiv_max_index pop ECX ; в ECX - ширина разрыва (Gap) между обменивающимися шариками, ; сначала равна длине массива, затем будет уменьшаться .WHILE 1 ; начало бесконечного цикла mov EDX, 0 ; EDX - индекс для шариков в левой части массива mov EBX, ECX ; EBX - индекс для шариков в правой части массива mov counter, 0 ; обнуляем счетчик обменов .WHILE ebx <= massiv_max_index ; пока индекс справа не дойдет до конца массива mov EAX, massiv[EBX*4] ; засылаем в EAX значение правого элемента .IF massiv[EDX*4] > EAX ; если значение левого элемента больше, чем EAX push EAX ; тогда совершаем обмен через стек push massiv[EDX*4] pop massiv[EBX*4] pop massiv[EDX*4] inc counter ; увеличиваем счетчик обменов .ENDIF inc EBX ; увеличиваем индекс правых inc EDX ; увеличиваем индекс левых .ENDW .IF counter == 0 && ECX == 1 ; проверяем, не пора ли прекратить работу .break .ENDIF .IF ECX <= 1 ; если Gap равен 1 или 0 mov ECX, 1 ; тогда Gap := 1 (пузырьковая сортировка) .ELSEIF mov EAX, ECX ; иначе Gap := Gap / 4 * 3 mov EDX, 0 div dwDiv4 mov EDX, 0 mul dwMul3 mov ECX, EAX .ENDIF .ENDW ; возврат на начало бесконечного цикла

Таблица. Время работы пузырьковой сортировки, эстафеты шариков и сортировки расческой
для периодических массивов одноразрядных десятичных чисел (9, 6, 3, 8, 5, 2, 7, 4, 1, 0...)

элементов
в массиве
пузырьковая
сортировка
эстафета
шариков
арифметическая
сортировка
расческой
(шаг = 100)
геометрическая
сортировка
расческой
(ус.фактор = /4*3)
10 0000,28 sec0,06 sec0,01 sec0,00 sec
50 0006,68 sec1,49 sec0,13 sec0,01 sec
100 00026,7 sec6,02 sec0,22 sec0,02 sec
200 000108 sec24,1 sec0,64 sec0,03 sec
300 000245 sec54,5 sec1,31 sec0,06 sec
400 000435 sec99,6 sec2,05 sec1,58 sec
500 000682 sec158 sec3,17 sec1,92 sec

     


Добавить комментарий

E-mail:
*


Контрольные цифры:



Ассемблер MASM32

      Простейшая программа на ассемблере (beeper)
      Переменные и типы данных ассемблера
      Регистры процессора IA32
      Консоль ввода-вывода
      API-функция CharToOem и строки ассемблера
      API-функция ReadConsoleInput
      API-функция PeekConsoleInput
      События консоли (таблица)
      Системы счисления, тэги ассемблера, перевод чисел
      Отрицательные числа
      Инкремент и декремент
      Деление (DIV, IDIV)
      VKDEBUG
      Макросы ассемблера
      Воспоминание об Альгамбре на системном динамике
      Командная строка
      Пузырьковая сортировка. Эстафета шариков
      Сортировка расческой
      Быстрая сортировка

     


© Max Petrov При использовании материалов ссылка на sadda.ru обязательна