Blog. Just Blog

Гномья сортировка массива на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Гномья сортировка массива на Ассемблере
Гномья сортировка массива на Ассемблере

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


Гномья сортировка основана на технике, используемой обычным голландским садовым гномом. Это метод, которым садовый гном сортирует линию цветочных горшков. Он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперед, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперед; если нет следующего горшка, он закончил.


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

Благодаря своей простоте, алгоритм гномьей сортировки легко реализуется практически на любом языке программирования. Вот мой вариант функции сортировки на Ассемблере:
  1. ;----------------------------------------------------------------
  2. ; Функция "гномьей сортировки" массива DWORD
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc gnome_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         ; В массиве меньше 2 элементов?
  13.         cmp     [dLen],2
  14.         jb      .loc_ret
  15.  
  16.         mov     esi,[lpArray]
  17.         xor     ecx,ecx
  18.         inc     ecx
  19. .loc_loop:
  20.         or      ecx,ecx
  21.         jz      @f
  22.         mov     eax,[esi+ecx*4-4]
  23.         mov     ebx,[esi+ecx*4]
  24.         cmp     eax,ebx
  25.         ; Для сортировки массива по убыванию замените
  26.         ; условный переход JBE на JAE
  27.         jbe     @f
  28.  
  29.         ; Поменять местами соседние элементы
  30.         mov     [esi+ecx*4-4],ebx
  31.         mov     [esi+ecx*4],eax
  32.         dec     ecx
  33.         jmp     .loc_loop
  34. @@:
  35.         inc     ecx
  36.         cmp     ecx,[dLen]
  37.         jb      .loc_loop
  38. .loc_ret:
  39.         popa
  40.         ret
  41. endp
Параметры вызова: lpArray - указатель на массив DWORD, который необходимо отсортировать, dLen - количество элементов в массиве, должно быть не менее двух. После отработки исходный массив будет отсортирован. Порядок сортировки определяется условным переходом, в приведенных примерах это сортировка по возрастанию. Для сортировки массива по убыванию замените в обозначенном месте условный переход JBE на JAE.

Сортировку можно заметно ускорить, если запоминать индекс крайнего неотсортированного элемента. После того как сделан ряд шагов назад, дальнейшую обработку массива необходимо продолжить с того места, где прервались. Я немного модифицировал предыдущую функцию, в результате получилась оптимизированная функция гномьей сортировки:
  1. ;----------------------------------------------------------------
  2. ; Функция оптимизированной "гномьей сортировки" массива DWORD
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc gnome_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         ; В массиве меньше 2 элементов?
  13.         cmp     [dLen],2
  14.         jb      .loc_ret
  15.  
  16.         mov     esi,[lpArray]
  17.         xor     ecx,ecx
  18.         inc     ecx
  19.         mov     edx,ecx
  20. .loc_loop:
  21.         or      ecx,ecx
  22.         jz      @f
  23.         mov     eax,[esi+ecx*4-4]
  24.         mov     ebx,[esi+ecx*4]
  25.         cmp     eax,ebx
  26.         ; Для сортировки массива по убыванию замените
  27.         ; условный переход JBE на JAE
  28.         jbe     @f
  29.  
  30.         ; Поменять местами соседние элементы
  31.         mov     [esi+ecx*4-4],ebx
  32.         mov     [esi+ecx*4],eax
  33.         dec     ecx
  34.         jmp     .loc_loop
  35. @@:
  36.         ; Перейти на крайний неотсортированный элемент
  37.         inc     edx
  38.         mov     ecx,edx
  39.         cmp     edx,[dLen]
  40.         jb      .loc_loop
  41. .loc_ret:
  42.         popa
  43.         ret
  44. endp
В приложении примеры программ с исходными текстами, сортирующие массив по возрастанию с помощью обычного и оптимизированного алгоритма.

Примеры программ с исходными текстами (FASM)Примеры программ с исходными текстами (FASM)

Gnome.Sort.Demo.zip (3,015 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 1676 | Комментариев: 6

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
ManHunter (31.03.2016 в 08:07):
uuu, садись, двойка.
http://asmworld.ru/uchebnyj-ku...eniya-metok/ , глава "Анонимные метки".
uuu (31.03.2016 в 00:06):
метка  @f  отсутствует, вместо нее @@
@@:
->
@f:
ManHunter (23.03.2016 в 15:30):
Так гигабайты никто "в лоб" и не сортирует без особой надобности. Индексы, сортировка частями, деревья и прочие оптимизации, это же не просто так придумано.
Андрей (23.03.2016 в 13:11):
Я не спорю, для общего круга задач это вполне приемлемо. Какой нибудь список там или базу данных упорядочить. Но если массив разрастается условно до гигабайта, то там сравнение каждого элемента уже роскошь. Время жрёт - караул!
Допустим всего десять неупорядоченных элементов это уже десять гиг сравнеий и передвижек.

ЦитатаДопустим всего десять неупорядоченных элементов это уже десять гиг сравнеий и передвижек.

Пардон. читать как "десять неупорядоченных элементов в конце списка это уже десять гиг сравнеий и передвижек."
ManHunter (23.03.2016 в 12:36):
Сто тысяч рандомных DWORD'ов сортирует быстрее, чем за пару секунд. Десяток тысяч - вообще без видимой паузы. И это не на топовом железе.
Андрей (23.03.2016 в 12:21):
Грусть - печаль такой сортировки в том что она хороша только для небольших массивов.

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

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2017
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.06 сек. / MySQL: 2 (0.0046 сек.) / Память: 4.5 Mb
Наверх