Сборник по задачам и примерам Assembler


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


dec ax

mov R.ax :R:=k-1

emp L.ax ;L>R - ?

jae $+5

jmp cycl3

Улучшение классических методов сортировки

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

Сортировка Шелла

Приводимый ниже алгоритм сортировки (программа prg4_107.asm) носит имя автора, который предложил его в 1959 году. Суть его состоит в том, что сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии h. На каждом шаге значение h изменяется, пока не станет (обязательно) равно 1. Важно правильно подобрать значения h для каждого шага. От этого зависит скорость работы алгоритма. В качестве значений h могут быть следующие числовые последовательности: (4, 2, 1), (8, 4, 2, 1) и даже (7, 5, 3, 1). Последовательности чисел можно вычислять аналитически. Так, Кнут предлагает следующие соотношения:

  • Nk-1 = 3Nk+1, в результате получается последовательность смещений: 1, 4, 13,40,121...
  • Nk-1, = 2Nk+l, в результате получается последовательность смещений: 1, 3, 7, 15, 31...

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

Отметим, что если h=1, то алгоритм сортировки Шелла вырождается в сортировку прямыми включениями.

Существует несколько вариантов алгоритма данной сортировки. Вариант, рассмотренный ниже, основывается на алгоритме, предложенном Кнутом.

ПРОГРАММА prg4_107

//prg4_107 - программа на псевдоязыке сортировки Шелла

//Вход: mas_dist=(7,5,3.1) - массив смещений: mas[n] - неупорядоченная

последовательность байтовых двоичных значений. //Выход: mas[n] -упорядоченная последовательность байтовых двоичных значений.

-ПЕРЕМЕННЫЕ

INT_BYTE t=4; //количество элементов в массиве смещений

INT_BYTE mas[n]; //сортируемый массив размерностью п (О..п-1)




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



Книжный магазин