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


 

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

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

      Алгоритм предложен Чарльзом Хоаром в 1960 году. Эффективность O(n log n) обменов при сортировке n элементов.

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

      Известным недостатком алгоритма является его рекурсивность, которая вызывает необходимость расходования памяти компьютера на запись адресов возврата из процедур сортировки каждого из подмассивов. Зависимость величины дополнительной памяти от числа элементов в исходном массиве характеризуется величиной n - 1.

.386 .model flat, stdcall option casemap :none include <\masm32\include\kernel32.inc> includelib <\masm32\lib\kernel32.lib> .data massiv dword 10000 dup (9,6,3,8,5,2,7,4,1,0) ; массив 100 000 чисел .code ;========================================================= ;========================================================= ; БЫСТРАЯ СОРТИРОВКА ; сортируются по возрастанию четырехбайтовые ; (dword) числа в диапазоне адресов массива от min до max; ; min - указатель на крайнее левое число; ; max - указатель на крайнее правое число qsort proc public uses EAX EBX EDX EDI ESI, \ min: ptr dword, max: ptr dword local dwDiv2: dword ; объявляем локальную переменную mov dwDiv2, 2 ; присваиваем ей значение "2" mov EDI, min ; в EDI - адрес левого mov ESI, max ; в ESI - адрес правого mov EAX, [EDI] ; в EAX - значение (не адрес) левого add EAX, [ESI] ; складываем EAX со значением правого mov EDX, 0 ; обнуляем EDX (подготавливаем для деления) div dwDiv2 ; делим EAX на "2" mov EBX, EAX ; в EBX - среднее значение левого и правого .WHILE EDI < ESI ; повторяем, пока адрес левого < адреса правого .WHILE [EDI] < EBX ; повторяем, пока значение левого < среднего значения add EDI, 4 ; увеличиваем адрес левого на 4 байта .ENDW .WHILE [ESI] > EBX ; повторяем, пока значение правого > среднего значения sub ESI, 4 ; уменьшаем адрес правого на 4 байта .ENDW .IF EDI <= ESI ; если адрес левого <= адреса правого push [EDI] ; тогда обмен значений через стек push [ESI] pop [EDI] pop [ESI] add EDI, 4 ; увеличиваем адрес левого на 4 байта sub ESI, 4 ; уменьшаем адрес правого на 4 байта .ENDIF .ENDW .IF min < ESI ; рекурсии влево invoke qsort, min, ESI .ENDIF .IF EDI < max ; рекурсии вправо invoke qsort, EDI, max .ENDIF ret ; возврат из процедуры qsort endp ;============================================================ ;============================================================ start: ; сортировка массива в диапазоне индексов 1000 - 2000 invoke qsort, addr massiv[1000*4], addr massiv[2000*4] ; сортировка массива в диапазоне индексов 0 - 99999 ;invoke qsort, addr massiv[0], addr massiv[99999*4] invoke ExitProcess, 0 end start

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

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

элементов
в массиве
быстрая
сортировка,
бейсик
сортировка
расческой
(ус.фактор = /4*3),
бейсик
быстрая
сортировка,
ассемблер
сортировка
расческой
(ус.фактор = /4*3),
ассемблер
10 0000,02 sec0,02 sec0,00 sec0,00 sec
50 0000,12 sec0,11 sec0,02 sec0,01 sec
100 0000,22 sec0,25 sec0,03 sec0,02 sec
200 0000,47 sec0,55 sec0,05 sec0,03 sec
300 0000,72 sec0,77 sec0,14 sec0,06 sec
400 0001,00 sec28,4 sec0,16 sec1,58 sec
500 0001,25 sec34,4 sec0,20 sec1,92 sec
1 000 0002,61 sec3,02 sec0,33 sec0,20 sec
10 000 00030,5 sec35,7 sec4,06 sec2,94 sec

     


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

E-mail:
*


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

   Валентина    13.11.2013    17:58
Огромное спасибо!
Успехов и удачи!


   Иван    16.11.2013    02:38
В таблице чуть выше допущены ошибки в последних двух строках столбцов "сортировка расчёской, бейсик" и "сортировка расчёской, ассемблер": вместо секунд время будет измеряться в минутах.


   Макс Петров    17.11.2013    00:41
В секундах. Сортировка расческой нестабильна, при ее использовании массив большего размера может сортироваться в разы быстрее массива меньшего размера. Зависимость как раз отражает такую особенность.


   Николай    02.09.2016    10:52
Для ассемблера это не предел, можно сделать еще быстрее, убрать рекурсию - заменив на стек, убрать часть ветвлений - заменив на cmov (минимализировав число промахов по предсказаниям переходов), выравнить метки nop-ами, есть еще куча оптимизаций (SSE интсрукции)...




Ассемблер MASM32

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

     


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