Assembler - язык неограниченных возможностей


Сортировки - часть 3


Рассмотрим в качестве примера самый простой вариант сортировки вставлением, использующий линейный поиск и затрачивающий порядка n2/2 операций. Ее так же просто реализовать, как и пузырьковую сортировку, и она тоже имеет возможность выполняться «на месте». Кроме того, из-за высокой оптимальности кода этой процедуры она может оказываться даже быстрее рассмотренной нами «быстрой» сортировки на подходящих массивах.

; Процедура linear_selection_sort ; сортирует массив слов методом сортировки линейным выбором ; Ввод: DS:SI (и ES:SI) = адрес массива ; DX = число элементов в массиве

do_swap: lea bx,word ptr [di-2] mov ax, word ptr [bx] ; новое минимальное число dec cx ; если поиск минимального закончился, jcxz tail ; перейти к концу loop1: scasw ; сравнить минимальное в АХ ; со следующим элементом массива ja do_swap ; если найденный элемент ; еще меньше - выбрать ; его как минимальный loop loop1 ; продолжить сравнения ; с минимальным в АХ tail:. xchg ax,word ptr [si-2] ; обменять минимальный элемент mov word ptr [bx],ax ; с элементом, находящимся в начале ; массива linear_selection_sort proc near ; точка входа в процедуру mov bx,si ; BX содержит адрес ; минимального элемента lodsw ; пусть элемент, адрес ; которого был в SI, минимальный, mov di,si ; DI - адрес элемента, сравниваемого ; с минимальным dec dx ; надо проверить DX-1 элементов массива mov cx,dx jg loop1 ; переход на проверку, если DX > 1 ret linear_selection_sort endp





Начало  Назад  Вперед