Главная » 1С Предприятие » БЫСТРАЯ СОРТИРОВКА

0

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

Рассмотрим  массив х:

25         37         12        33         48         57        92         86

В нем  число 48 характеризуется тем, что, во-первых, все расположенные левее него числа меньше 48 и, во-вторых, числа, расположенные правее него, больше 48. Назовем  такое   число разделителем  массива.  Нетрудно  понять,  что  теперь   мы  можем   отдельно  решать  задачу  сортировки  для  чисел до  разделителя  и  для  чисел  после   него.  Кроме  того, сам  разделитель  находится  в  нужной позиции,  то есть  в дальнейшей сортировке он уже не рассматривается.

Рассмотрим  теперь  массив, в котором нет разделителя:

37        25         57        48         12        92         86         33

Чтобы   воспользоваться   только   что  приведенной  идеей  уменьшения  размерности задачи  сортировки,  нам  надо  научиться  выполнять  такие перестановки в массиве,  после  которых один из его  элементов  станет  разделителем.   Выберем для  будущего  разделителя  первый  элемент массива,  то  есть  число  37.  Разделитель  окажется в  нужной позиции, если разместить  числа 25,  12 и 33 слева от 37. Выполним  это так:  будем просматривать последовательно  элементы массива начиная  с  его  первой  позиции  до  тех пор, пока  не  встретим  число,  большее разделителя.  Присвоим этой  позиции  имя L1. Далее  просмотрим  элементы массива начиная  с  последней позиции,  останавливаясь при  обнаружении  числа,  меньшего 37. Дадим такой  позиции  имя R1.  В нашем случае после выполнения  этих двух просмотров возникнет следующая ситуация:

Нетрудно предугадать следующий  шаг  алгоритма  числа 57 и  33 должны быть  переставлены  местами, тогда  получится  массив

Продолжим   теперь   поиск  элемента,  большего  37, перемещаясь  вправо,  начиная с позиции L1, и элемента, меньшего 37, перемещаясь влево, начиная с позиции R1. Такой  поиск даст  следующий  результат:

Выполним  и перестановку:

37

25

33

12

48

92

86

57

L1

R1

Еще  одна  пара  перемещений не изменит картины, но  даст нам  основание для пре­

кращения  левых и  правых  перемещений вдоль массива (критерий прекращения  перемещений  истинность  выражения  L1  >= R1)  и  перестановки  разделителя  (числа 37) в его окончательную позицию. После выполнения  перемещений, предшествующих  перестановке  разделителя, имена R1  и L1 расположатся так:

Сам  же разделитель  должен быть  размещен в  позиции  R1, что  выполняется в результате  обмена элементов х[1] и x [R1] , то есть чисел 12 и 37. Приведем и результат:

12         25         33         37        48        92         86         57

Итак, массив разбит на две части  (до и после  разделителя), которые можно сортировать отдельно, применяя  к каждой из частей  только  что  приведенную  схему.  Завершим же сортировку,  когда  длина каждой из полученных в результате разбиения частей  будет равна единице.

Замечание.    Выбор   в   качестве   будущего   разделителя   первого   элемента   массива (или  последующего  фрагмента)  необязателен  и   в  ряде   случаев  неудовлетворителен. Так, в случае  почти  отсортированного массива будущий  разделитель  лучше  выбирать ближе к середине рассматриваемого  фрагмента.

Вычислительная   сложность  быстрой  сортировки  оценивается  как   0(nlog2n).  Так, если  сортируется  массив  из  1024 элементов, то пузырьковая сортировка будет  в  среднем выполняться в

раза медленнее.

Источник: Бартеньев О. В. 1С:Предприятие:  программирование для  всех.  Базовые объекты и расчеты на одной дискете. М.: Диалог-МИФИ, 2005. 464 с.

По теме:

  • Комментарии