Главная » Basic » СОРТИРОВКА С ПОМОЩЬЮ ИНДЕКСА

0

Требующийся для любой сортировки обмен значениями на некоторых ЭВМ может занимать много времени, если надо обмениваться строками или если  несколько массивов рассматриваются  как один логический элемент. Однако вместо переупорядочения  самих значений в процессе сортировки можно образовать индекс (предметный указатель), в  котором отмечаются правильные  места значений в массиве.  Во время сортировки  значения остаются на исходных местах, а изменяется  индекс. По окончанию  сортировки индекс используется для копирования сортируемых значений в новый  массив или служит справочником для работы с исходным массивом.

Если нам требуется отсортировать   массив А(100)  ,  то  надо ввести  индекс I(100)  ,  лучше  всего целочисленный, если такая  возможность предусмотрена  в   системе (это  сократит занимаемую массивом память), и задать начальные значения его элементов операторами

FOR L = 0 TO 100

I(L) =L NEXT L

Для индекса должно выполняться соотношение I (исходная позиция) = новая позиция

поэтому перед началом сортировки I(1)=1, I(2)=2 и  т. д. При сортировке  во время  каждого прохода сравниваются значения  из А, определенные по I( ) , а переставляются значения индекса в I( ) .

При введении индекса  программа для сортировки методом пузырька из подразд. 4.5.1 превратится в следующую программу:

распечатают исходный, неизмененный набор значений, а операторы FOR L = 1 ТО N PRINT A (I1) NEXT L

распечатают отсортированный набор значений.

Применение индекса дает большое преимущество в случае, когда значения данных распределены по нескольким  массивам. Если, скажем, сортируются значения массивов А (10), В(9), С(27), то можно создать индекс I(46), в  котором первые 10 элементов указывают на массив А, следующие 9 — на массив В, а последние 27 — на С. Конечно, алгоритм надо модифицировать так, чтобы в сравнениях могли участвовать как элементы массива А, так и элементы массивов В и С.

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

Источник: Уолш Б.    Программирование на Бейсике: Пер. с англ. М.: Радио и связь, 1988. 336 с: ил.

По теме:

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