Blog. Just Blog

Сортировка вставками на Ассемблере

13.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка вставками - это алгоритм сортировки, который преобразует массив данных путем поочередного включения каждого элемента в упорядоченную последовательность элементов. Он подразумевает разделение массива на отсортированную и неотсортированную части. На каждом шаге из неотсортированной части выбирается элемент и вставляется в правильное место в отсортированной части. И так продолжается до тех пор, пока весь набор входных данных не будет отсортирован.

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

Читать статью целиком »
Просмотров: 152 | Комментариев: 0

Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 1 (0.0104 сек.) / Память: 4.5 Mb
Наверх