Реализация поразрядной сортировки

Пусть имеем список, элементами которого являются записи (для удобства буду вести повествование в терминах Паскаля) с тремя полями:

1) Указатель на следующий элемент списка

2) Ключ

3) Данные

Несколько необычный порядок полей не должен вас смущать. Это сделано для быстродействия (поможет избежать лишних операций сложения, ниже будет подробно рассмотрен код сортировки, всё поймёте).

Пусть для определённости данные и ключи – 32-разрядные беззнаковые целые числа. Такой тип данных выбран также и для лучшего понимания происходящего. С ним процессор компьютера на "ты" – 32-битные числа можно спокойно хранить в регистрах процессора и сравнивать на больше-меньше, чего нельзя сказать, к примеру, о строках, для хранения которых требуется отведение оперативной памяти, нужны усложнённые способы сравнения и т. д., в общем, всё сложнее.

Идея с 10 карманами (как в описанном выше примере), на мой взгляд, неудачна для реализации. Для человека привычна десятичная система счисления, компьютер же "понимает" двоичную. Чтобы заставить его понимать десятичную систему счисления, потребуются многочисленные операции деления на 10 и взятия остатка по модулю 10, а, как известно, операции эти затратны по времени. Двоичная система, которую "понимает" компьютер тоже не совсем удачна. В случае сортировки 32-разрядных чисел по списку мы пройдём 32 раза! На мой взгляд, многовато :) И потом, просматривать отдельный разряд также не очень удобно. Поэтому остановимся на 256 карманах от 0 до 255, то есть будем сортировать как бы 4-разрядные числа в системе счисления по основанию 256.

В массиве карманов будем хранить 32-разрядные указатели (адреса первых элементов карманов), то есть нам потребуется 4*256 байт памяти. В погоне за скоростью я считаю вполне разумным решение пожертвовать ещё килобайтом памяти. В своей реализации я предусмотрел ещё один массив, в котором хранятся последние элементы карманов. При таком раскладе намного удобнее осуществить сцепление карманов (последний элемент предыдущего стыкуется с первым элементом следующего).

Приступаем к реализации алгоритма. Заодно укрепим ассемблерные навыки. Комментарии я постарался выдержать в духе Turbo Pascal, поэтому сложностей не должно возникнуть.

Компилятор MASM был взят с сайта wasm.ru.



include masm32.rt
.data
  ha dword ?; дескриптор кучи
  n dword ?; количество элементов списка
.code
  randval proc uses ebx
    ; Процедура, помещающая в регистр ЕАХ случайное число.
    ; Так как о существовании библиотек с генераторами случайных 
    ; чисел на момент написания программы я не знал, то написал эту процедуру.
    db 15, 49; эта команда помещает в регистр ЕАХ число прошедших с момента
             ; включения компьютера тактов процессора, но так как при каждом
             ; новом вызове мы будем получать значение, большее предыдущего,
             ; то сгенерированный таким образом массив будет уже отсортирован.
             ; Поэтому применяем к числу в ЕАХ хэш-функцию, найденную на
             ; просторах интернета по незатейливому запросу.
    mov ebx, eax
    shl ebx, 15
    not ebx
    add eax, ebx
    mov ebx, eax
    shr ebx, 10
    xor eax, ebx
    mov ebx, eax
    shl ebx, 3
    add eax, ebx
    mov ebx, eax
    shr ebx, 6
    xor eax, ebx
    mov ebx, eax
    shl ebx, 11
    not ebx
    add eax, ebx
    mov ebx, eax
    shr ebx, 16
    xor eax, ebx
    and eax, 7fffffffh; все числа делаем положительными. Это нужно для удобства просмотра результатов.
    ret; не забываем об этой коварной (при своём отсутствии) команде!
  randval endp
  ladd proc uses ecx
    ; процедура добавления элемента в список
    invoke HeapAlloc, ha, HEAP_ZERO_MEMORY, 12; выделяем 12 байт динамической
      ; памяти в куче с дескриптором ha с помощью API-функции HeapAlloc.
      ; результат функции - адрес выделенного участка памяти - помещается
      ; в регистр ЕАХ
    mov [eax], esi; условимся, что ESI - указатель на начало списка.
    mov esi, eax
    call randval; в ЕАХ заносим случайное число
    mov [esi+4], eax; записываем в поле ключа случайное число
    call randval; в ЕАХ снова случайное число
    mov [esi+8], eax; заполняем поле данных
    ret
  ladd endp

Процедуру вывода списка на экран предлагаю читателям написать самостоятельно. А теперь процедура, ради которой мы здесь собрались.


lsort proc
    local a[256]: dword, b[256]: dword; a и b - массивы указателей на первые и последние элементы 
    карманов соответственно
    test esi, esi                     ; проверка списка на "NIL"
    jz @exit                          ; список пуст, сортировать нечего - выходим из процедуры
    mov ebx, 4                        ; в ЕВХ заносим число 4 - смещение ключа. Почему 4? Потому что
                                      ; первые 4 байта записи
                                      ; отведены под адрес следующего элемента, и для того, чтобы 
                                      ; попасть на младший байт ключа,
                                      ; нужно "перепрыгнуть" через адрес следующего элемента. Ключ 
                                      ; занимает 4-й - 7-й байты записи
                                      ; (отсчёт ведётся с нуля)
    .repeat
      xor eax, eax                    ; обнуляем ЕАХ
      mov ecx, 256                    ; ЕСХ:=256
      lea edi, a                      ; кладём в EDI адрес массива а
      rep stosd                       ; обNILяем массив а
      mov ecx, 256
      lea edi, b
      rep stosd                       ; обNILяем массив b
      .while esi!=0                   ; проходим по элементам списка
        movzx edi, byte ptr [esi+ebx] ; помещаем в EDI значение (ЕВХ-3)-го байта ключа: на первой 
                                      ; итерации
                                      ; это будет младший байт ключа, на второй - следующий по 
                                      ; старшинству и так далее вплоть до
                                      ; старшего байта - т. е. всего 4 раза
        shl edi, 2                    ; умножаем EDI на 4, сейчас поймёте зачем
        lea ecx, b                    ; в ЕСХ помещаем адрес массива b (т. е. по сути адрес его 
                                      ; нулевого элемента)
        add ecx, edi                  ; а теперь в ECX находится адрес последнего элемента нужного 
                                      ; нам кармана (пусть он имеет индекс i),
                                      ; т. е. "b[i]". Умножение на 4 было нужно для вычисления этого  
                                      ; адреса (помним, что
                                      ; адреса - 32-разрядные (4-байтовые) целые числа).
        mov edx, [ecx]                ; помещаем в EDX само значение "b[i]"
        .if edx==0                    ; если карман пуст ("b[i]=NIL")...
          lea eax, a                  ; вычисляем адрес нулевого кармана массива а
          add eax, edi                ; вычисляем адрес i-го кармана массива а
          mov [eax], esi              ; "a[i]:=list"
        .else                         ; иначе...
          mov edx, [ecx]              ; EDX - адрес следующего элемента списка
          mov [edx], esi              ; ... "b^.next:=list"
        .endif
        mov [ecx], esi                ; "b[i]:=list"
        mov esi, [esi]                ; очень изящный способ выполнения операции, аналогичной 
                                      ; паскалевской "list:=list^.next".
                                      ; Теперь становится понятно, для чего я выбрал "нестандартный"
                                      ; порядок полей - экономия времени 
                                      ; (пусть и незначительная) благодаря отсутствию операций  
                                      ; сложения.
        mov edx, [ecx]                ; в EDX помещаем адрес b[i]
        xor edi, edi                  ; обнуляем EDI
        mov [edx], edi                ; "b[i]^.next:=NIL"
      .endw
 ; Карманы заполнены, теперь их нужно склеить
      lea eax, a
      lea ecx, b                      ; помещаем в ЕАХ и ЕСХ адреса а и b соответственно
      mov edx, [eax]                  ; "EDX:=a[0]"
      .while edx==0                   ; ищем первый непустой карман (непустым будет тот, первый 
                                      ;(или последний, это непринципиально)
                                      ; элемент которого не равен "NIL". Моя программа просматривает 
                                      ; первые элементы).
        add eax, 4
        add ecx, 4
        mov edx, [eax]
      .endw
      push edx                        ; EDX - адрес первого непустого кармана, он же впоследствии 
                                      ; будет адресом первого элемента "склеенного" списка
      mov esi, [ecx]                  ; перемещаем указатель на последний элемент первого непустого 
                                      ; кармана
      lea edx, a                      ; в EDX кладём адрес массива а (или его 0-го элемента)
      add edx, 1024                   ; а теперь - адрес его последнего (255-го) элемента
      add eax, 4
      add ecx, 4                      ; начинаем с (i+1)-го кармана...
      
      .while eax < edx                ; ... и идём до 255-го
        mov edi, [eax]
        test edi, edi                 ; проверка на "NIL"
        jz @skip                      ; если карман непуст...
          mov [esi], edi              ; ... то "list^.next:=a[i]" - присоединяем карман к предыдущему
          mov esi, [ecx]              ; "list:=b[i]" - перемещаем указатель на конец получившегося 
                                      ; списка
        @skip:
        add eax, 4
        add ecx, 4                    ; переходим на следующий карман
      .endw
      pop esi                         ; вспоминаем адрес первого элемента полученного списка
      inc ebx                         ; берём следующий по старшинству байт
    .until ebx > 7                    ; и повторяем цикл для этого байта
  @exit:
    ret                               ; сортировка закончена
  lsort endp

Осталось написать главную процедуру main. Те, кто дошёл до этого места, думаю, справятся с этой задачей. Подсказка: дескриптор кучи можно получить с помощью API-функции GetProcessHeap, синтаксис которой прост:

  invoke GetProcessHeap; в результате имеем в ЕАХ дескриптор кучи.



© Бараев Николай Михайлович