Виды сортировки (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:40, 9 августа 2015.

Алгоритмы сортировки (ASM x86)

Существует множество различных алгоритмов сортировки. Все они имеют свои плюсы и минусы, так что "идеальный алгоритм",зависит от потребностей пользователя. В качестве примера рассмотрим 3 различных алгоритма: гномью сортировку(Gnome Sort), сортировку методом вставок(Insertion Sort) и быструю сортировку(Quicksort). В качестве теста сделаем версии этих алгоритмов на C + +, сравним их скорости, по возможности попробуем улучшить при компиляции.

Перейдем непосредственно к сортировкам.


Gnome Sort (Гномья сортировка)

Самый медленный, но простейший алгоритм в этом списке. Он сочетает в себе сортировку вставками и пузырьковую сортировку. Как уже упоминалось, алгоритм не очень быстрый, но размер кода крошечный по сравнению с другими алгоритмами.

Gnome Sort является хорошим введением в алгоритмы сортировки, но на практике лучше использовать более быстрые и эффективные алгоритмы. Имеет в среднем и в худшем случае время работы O (n ^ 2).

Плюсы: Крошечный размер кода. Очень легко понять.
Минусы: довольно медленный по сравнению с другими алгоритмами.

Описание

Gnome sort -это очень простой алгоритм сортировки, который сочетает в себе сортировку методом вставки и пузырьковую сортировку. Размер кода небольшой и достаточно понятный, алгоритм устойчив и использует только одну петлю. К сожалению, не очень быстр по сравнению с другими алгоритмами.

Он был изобретен Хамидом Сабази-Азадом (Hamid Sarbazi-Azad) в 2000 году.

Алгоритм работает следующим образом:

По сути, в алгоритме сравниваются рядом стоящие элементы, если они стоят в нужном порядке, тогда мы переходим на следующий элемент массива, если нет, ты мы их переставляем и переходим на предыдущий. Нету предыдущего элемента — идём вперед, нету следующего — значит мы закончили. Изначально мы находимся на втором элементе массива.


Этот алгоритм имеет в лучшем случае скорость О (n), а в среднем и худшем- O (n ^ 2).

При необходимости более быстрого алгоритма смотрите сортировку методом вставки (Insertion Sort) или быструю сортировку (Quicksort).

Код

ПРИМЕЧАНИЕ: используется для сортировки массива из 4 байтных типов данных. Для того чтобы сохранить алгоритм как можно более простыми для этого примера, массив перемещается с шагом, равным 4. Если вы хотите использовать этот алгоритм для сортировки предметов из меньших или больших типов данных, правильным решением было бы использовать размер данных в качестве параметра и использовать его при обходе массива.

.386
.model flat, c
.code

;Код Мигеля Касильяса.
;This code can be used and reproduced, please give credit

;void GnomeSort(void *pArray, int nItems);
GnomeSort PROC

    ;These registers must be restored at the end
    push EBP
    mov  EBP, ESP
    push EBX
    push ESI
    push EDI
   
    ;EBP + 8    массив
    ;EBP + 12   кол-во элеметов в массиве

    mov ESI, [EBP+8]    ;ESI это массив
    mov ECX, [EBP+12]   ;установка ECX к кол-ву элементов
    xor EAX, EAX        ;установка EAX до 0, это будет наш итератор
   
    MainLoop:
        ;если 'i' >= кол-ву элементов, выходим из цикла
        cmp EAX, ECX
        jge EndLoop    
       
        ;если 'i' == 0, переходим к следующему элементу
        cmp EAX, 0
        je IncreaseCounter
       
        ;если массив [i-1] <= массив[i], означает,что они сортируются
        ;переходим к следующему элементу
        mov EBX, [ESI]      ;EBX = array[i]
        mov EDX, [ESI-4]    ;EDX = array[i-1]
        cmp EDX, EBX
        jle IncreaseCounter
       
        ;иначе поменяем местами массив[i-1] с массивом[i]
        push [ESI]
        push [ESI-4]
       
        pop [ESI]
        pop [ESI-4]
       
        ;переходим к предыдущему элементу массива
         уменьшаем'i'
        sub ESI, 4
        dec EAX
       
        ;Loop back to the top
        BackToMainLoop:
        jmp MainLoop
       
        ;переходим к следующему элементу массива
         увеличиваем 'i'
    IncreaseCounter:
        inc EAX
        add ESI, 4
        jmp BackToMainLoop
   
    EndLoop:
   
    ;Restoring the registers
    pop EDI
    pop ESI
    pop EBX
    pop EBP

    RET
GnomeSort ENDP

END

Результаты

Среднее время сортировки списка из 10 000 случайных целых чисел- 0,1484936 секунды, что почти так же, как и на скомпилированной версии этого алгоритма на C + +.

Insertion Sort (Сортировка методом вставки)

Как следует из названия, этот алгоритм использует способ вставки (в отличие от метода замены гномьей сортировки), чтобы отсортировать список. Быстрее, чем Gnome Sort и код не намного больше. Имеет в среднем и худшем случае время работы O (n ^ 2).

Плюсы: Хорошо подходит для небольших списков.
Минусы: не очень эффективен для больших списков.

Описание

Алгоритм сортировки методом вставки принимает каждый элемент и помещает его в отсортированном списке.

Алгоритм работает следующим образом:

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

В лучшем случае скорость O (n), в среднем и худшем- O (n ^ 2).

При необходимости более быстрого алгоритма используйте алгоритм быстрой сортировки.

Код

ПРИМЕЧАНИЕ: используется для сортировки массива из 4 байтных типов данных. Для того чтобы сохранить алгоритм как можно более простым для этого примера, массив перемещается с шагом, равным 4. Если вы хотите использовать этот алгоритм для сортировки предметов из меньших или больших типов данных, правильным решением было бы использовать размер данных в качестве параметра и использовать его при обходе массива.

.386
.model flat, c
.code

;Код Мигеля Касильяса.
;This code can be used and reproduced, please give credit

;void InsertionSort(void *pArray, int nItems);
InsertionSort PROC

    ;These registers must be restored at the end
    push EBP
    mov  EBP, ESP
    push EBX
    push ESI
    push EDI
   
    ;EBP + 8    массив
    ;EBP + 12   кол-во элементов в массиве

    ;установка ECX к кол-ву элементов
    ;умножаем на 4 (размер элемента), чтобы поместить ECX
    ;на последний адресс массива
    mov EAX, [EBP+12]  
    mov ECX, 4
    mul ECX
    mov ECX, EAX         
   
    ;будем перемещать 'i' и 'j' с шагом,равным 4,
    ;который равен размеру элеметов
    mov EAX, 4          ;EAX будет нашим'i'
    xor EBX, EBX        ;EBX будет 'j' (устанавливаем в 0)
    mov ESI, [EBP+8]    ;ESI массив

    MainLoop:
        ;если 'i' >= кол-ву элементов, выходим из цикла
        cmp EAX, ECX
        jge EndLoop
       
        ;сохраняем наше "кол-во элементов"
        push ECX
       
        ;ECX теперь наш "ключ", так что, ECX = массив[i]
        mov ECX, [ESI+EAX]
       
        ;j = i-1
        mov EBX, EAX
        sub EBX, 4
       
        EnterWhile:
            ;если j < 0, выходим из цикла
            cmp EBX, 0
            jl EndWhile
           
            ;если массив[j] <= ключу, выходим из цикла
            cmp [ESI+EBX], ECX
            jle EndWhile
           
            ;массив[j+1] = массив[j]
            push [ESI+EBX]
           
            pop [ESI+EBX+4]
           
            ;j--
            sub EBX, 4
           
            ;Go back to the top of this loop
            jmp EnterWhile
           
        EndWhile:
       
        ;массив[j+1] = ключ
        mov [ESI+EBX+4], ECX
       
        ;i++
        add EAX, 4
       
        ;восстановим наше "кол-во элементов"
        pop ECX
       
        ;Go back to the top of this loop
        jmp MainLoop
       
    EndLoop:
   
    ;Restoring the registers
    pop EDI
    pop ESI
    pop EBX
    pop EBP

    RET
InsertionSort ENDP

END

Результаты

Среднее время сортировки списка из 10 000 случайных целых чисел - 0,07452373 секунд, что почти в 2 раза меньше,чем у алгоритма гномьей сортировки, но ,к сожалению, не так быстро, как у скомпилированной версии алгоритма на C + +.

Quicksort (Быстрая сортировка)

Самый быстрый алгоритм из данных трех. Использует метод "разделяй и властвуй", что означает, что он разбивает список рекурсивно и сортирует его. Имеет в среднем случае O (n log n), в худшем, по-прежнему, O (n ^ 2).

Плюсы: Очень быстрый.
Минусы: Нестабильный.

Описание

QuickSort является очень быстрым и эффективным алгоритмом сортировки "разделяй и властвуй" и был изобретен Тони Хоаром (Tony Hoare) в 1960 году в Московском государственном университете.

Алгоритм работает следующим образом: Во-первых, выбирается точка опоры (в данном примере, мы будем использовать низкий показатель). Затем с ней сравниваются элементы массива, и перемещаются налево или направо. После того,как это будет сделано, массив будет разделен на две части, а функция будет вызываться рекурсивно, пока все элементы не отсортируются.

В лучшем случае и в среднем скорости - O (n log n), но в худшем- O (n ^ 2). Кроме того, алгоритм не стабилен. В случае сортировки целых чисел, это не имеет значения, но если мы сортируем тип данных, где весь ключ это не весь элемент, то стабильность уже "вступает в игру".

Код

ПРИМЕЧАНИЕ: используется для сортировки массива из 4 байтных типов данных. Для того чтобы сохранить алгоритм как можно более простыми для этого примера, массив перемещается с шагом, равным 4. Если вы хотите использовать этот алгоритм для сортировки предметов из меньших или больших типов данных, правильным решением было бы использовать размер данных в качестве параметра и использовать его при обходе массива.

.386
.model flat, c
.code

;Код Мигеля Касильяса.
;This code can be used and reproduced, please give credit

;void QuickSort(void *pArray, int nItems);
QuickSort PROC

    ;These registers must be restored at the end
    push EBP
    mov EBP, ESP
    push EBX
    push ESI
    push EDI
   
    ;EBP + 8    массив
    ;EBP + 12   кол-во элементов в массиве
   
    mov ESI, [EBP+8]    ;ESI массив
   
    ;устанавливаем ECX кол-во элементов
    ;умножаем на 4 (размер элемента), чтобы поместить ECX
    ;на последний адрес массива
    mov EAX, [EBP+12]
    mov ECX, 4
    mul ECX
    mov ECX, EAX
   
    ;EAX будет нашим  'нижним индексом', изначально утсановили в 0
    xor EAX, EAX
   
    ;EBX будет нашим 'верхним индексом', изначально установили на
    ;последний элемент массива  настоящее время хранится в ECX)
    mov EBX, ECX
   
    ;теперь вызываем нашу рекурсивную функцию, которая будет сортировать массив
    call QuickRecursive
       
    ;Restoring the registers
    pop EDI
    pop ESI
    pop EBX
    pop EBP

    RET
QuickSort ENDP


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Рекурсивная функция сортировки
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
QuickRecursive:
   
    ;если нижний индекс >= верхний индекс, выходим из функции
    cmp EAX, EBX
    jge PostIf
   
    push EAX    ;сохраняем наш нижний индекс,теперь EAX это 'i'
    push EBX    ;сохраняем наш верхний индекс, теперь EBX это 'j'
    add EBX, 4  ;j = high + 1
   
    ;EDI точка опоры
    ;точка опоры = массив[нижнИндексы];
    mov EDI, [ESI+EAX]
   
    MainLoop:

        iIncreaseLoop:
           
            ;i++
            add EAX, 4
           
            ;если i >= j, выходим из цикла
            cmp EAX, EBX
            jge End_iIncreaseLoop
           
            ;если массив[i] >= точка опоры, выходим из цикла
            cmp [ESI+EAX], EDI
            jge End_iIncreaseLoop
           
            ;Go back to the top of this loop
            jmp iIncreaseLoop

        End_iIncreaseLoop:
       
        jDecreaseLoop:
       
            ;j--
            sub EBX, 4
           
            ;If array[j] <= pivot, exit this loop
            cmp [ESI+EBX], EDI
            jle End_jDecreaseLoop
           
            ;Go back to the top of this loop
            jmp jDecreaseLoop

        End_jDecreaseLoop:
       
        ;если i >= j, не меняем и заканчиваем основной цикл
        cmp EAX, EBX
        jge EndMainLoop
       
        ;иначе, меняем массив [i] с [j]
        push [ESI+EAX]
        push [ESI+EBX]
       
        pop [ESI+EAX]
        pop [ESI+EBX]
       
        ;Go back to the top of the main loop
        jmp MainLoop
       
    EndMainLoop:       
   
    ;восстанавливаем верхний индекс в EDI
    pop EDI
   
    ;восстанавливаем нижний индекс в ECX
    pop ECX
   
    ;если нижний индекс == j, не меняем
    cmp ECX, EBX
    je EndSwap
   
    ;иначе, меняем массив[нижних индексов] с массивом[j]
    push [ESI+ECX]
    push [ESI+EBX]
       
    pop [ESI+ECX]
    pop [ESI+EBX]
       
    EndSwap:

    ;устанавливаем EAX назад в нижний индекс
    mov EAX, ECX
   
    push EDI    ;сохраняем верхний индекс
    push EBX    ;сохраняем j
   
    sub EBX, 4  ;устанавливаем EBX в j-1
   
    ;QuickSort(array, low index, j-1)
    call QuickRecursive
   
    ;Restore 'j' into EAX
    pop EAX
    add EAX, 4  ;setting EAX to j+1
   
    ;Restore the high index into EBX
    pop EBX
   
    ;QuickSort(array, j+1, high index)
    call QuickRecursive
   
    PostIf:

RET

END

Результаты

Среднее время сортировки списка из 10 000 случайных целых чисел - 0,0007905865 секунды, что составляет около 1% времени сортировки методом вставки, и около 0,5% времени гномьей сортировки. Кроме того, эта версия сортировки такая же быстрая, как и скомпилированная версия алгоритма на C + +.

Сравнение

Алгоритмы были протестированы при сортировке 100 списков из 10000 случайных чисел. Сравнили их с C + + версиями, в результате их всех можно сделать примерно с одной и той же скоростью, за исключением сортировки методом вставки, которая оказалась медленнее C + +-версии.

Вот среднее время, в секундах, которое потребовалось каждому алгоритму для сортировки 10000 случайных целых чисел, в порядке от быстрых к медленным:

Quicksort 0,0007905865 секунд
Insertion Sort 0.07452373 секунд
Gnome Sort 0.1484936 секунд