Главная » 1С Предприятие » СОРТИРОВКА ТАБЛИЦЫ УКАЗАТЕЛЕЙ

0

Рис. 9.2. Отсортированная таблица указателей

При  работе   с  таблицами  указателей  задача  поиска  записи  решается  в  два  этапа:

1) в таблице указателей ищется ключ;  2) в файле  данных  ищется запись (по  ее номеру), с которой связан найденный в таблице указателей ключ.

Рассмотрим   теперь   алгоритмы   внутренней   пузырьковой  и   быстрой   сортировки ключей. Расширение этих методов  для  сортировки  записей  файла  или  таблицы  указателей  представляется очевидным.

9.1.3.  СОРТИРОВКА МАССИВА МЕТОДОМ ПУЗЫРЬКА

Сортировка методом  пузырька наиболее проста  для реализации,  но  имеет незначительную  вычислительную эффективность.

Не  теряя  общности, будем  для  простоты изложения  в  дальнейшем  рассматривать задачу  сортировки  массива х целых  чисел,  в  котором первые  п  чисел  должны  быть  от­

сортированы так, чтобы  для 

Идея  сортировки  методом  пузырька в  том, чтобы  просмотреть массив  последова­

тельно  несколько раз.  Один просмотр состоит из сравнения каждого  элемента массива со следующим  за ним элементом (xi   сравнивается с  xi+1)  и  обмена  этих двух элементов, если  они располагаются не в  нужном порядке (если  xi>  хi+1).

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

25

57        48

37

12

92

86

33.

Результат  сортировки:

12

25        33

37

48

57

86

92.

Проанализируем  процесс сортировки.

Н а перво м просмотр е делаютс я сравнения :

x1   c x2

(25 с 57)

Нет обмена

х2  с х3

(57 с 48)

Обмен

х3

с

х4

(57 с 37)

Обмен

х4

с

х5

(57 с 12)

Обмен

х5

с

х6

(57 с 92)

Нет обмена

х6

с

х7

(92 с 86)

Обмен

х7

с

х8

(92 с 33)

Обмен

После   первого  просмотра  в  результате   обменов  элементы  массива  расположатся

в таком  порядке:

25    48     37     12     57     86    33     92

Отметим, что  наибольший  элемент (в  данном случае  92)  находится  после  первого просмотра  в   нужной  позиции.  В  общем   случае   элемент    xn-pass+1           результирующего  массива будет  находиться  в  нужной позиции  после  итерации pass.  Отсюда  и  идет название метода:   каждое  число  медленно  "всплывает",  как  пузырек, вверх на  свою  конечную  позицию.

После  второго просмотра в результате  обменов элементы массива расположатся так:

25     37     12    48     57    33     86    92

Как  и  ожидалось, в  нужной позиции  оказалось второе по  величине число,  86.  Поскольку каждая  итерация помещает в  нужную  позицию очередной элемент,  для  сортировки массива из и чисел потребуется не более п 1 итераций.

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

Массив до начала  сортировки

25  57  48  37  12  92  86  33

Итерация  1

25  48  37  12  57  86  33  92

Итерация  2

25  37  12  48  57  33  86  92

Итерация  3

25  12  37  48  33  57  86  92

Итерация  4

12  25  37  33  48  57  86  92

Итерация  5

12  25  33  37  48  57  86  92

Итерация  6

12  25  33  37  48  57  86  92

Итерация  7

12  25  33  37  48  57  86  92

В  каждой   строчке  приведенного  списка  итераций подчеркнуты элементы  массива,

находящиеся  в нужной позиции.

Анализ полного набора  итераций подсказывает  два очевидных улучшения  метода.

Во-первых, поскольку все элементы в  позициях к> п pass +  1  уже  находятся  после  итерации pass на  нужных   местах, их  рассмотрение на  последующих  итерациях избыточно.  Следовательно,  на  каждой   итерации  число  необходимых  сравнений  уменьшается  на единицу. Так, при первом просмотре нужно  сделать  п 1 сравнений, на втором  и  2, на  просмотре с  номером pass  только п  pass.  To  есть  данный  процесс ускоряется с каждым  просмотром.

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

тельно  к  нашему примеру  это  означает, что  факт  завершения  сортировки  будет  установлен только  на шестом проходе.

Проанализируем   вычислительную  эффективность  метода.   Всего   алгоритм  (без усовершенствований)  предусматривает   выполнение   п   -1  просмотров   и   и   -1   сравнений на каждом просмотре. Таким образом, общее  число сравнений на всех  возможных  проходах равно (n 1)*(n -1) = п2  2n + 1, что составляет  0(п2).

Введенные  усовершенствования метода  хотя  и  сокращают общее  число сравнений, но  не  изменяют  порядка вычислительной  сложности.  В самом  деле,  число сравнений на итерации pass равно n pass. При наличии к итераций общее число сравнений равно (n -1)  + (n 2) + … + (n k) (2k*п  k2   k)/2. Можно  показать, что  среднее число итераций k представляет  собой  0(п),  так  что  общая  формула имеет по-прежнему порядок 0{п2),  хотя постоянный сомножитель теперь  меньше, чем ранее.

Если  массив  полностью  отсортирован, то  вычислительная  сложность метода  составляет 0(п) необходимо  л 1 сравнений, чтобы  в этом  убедиться.

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

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

По теме:

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