СОРТУВАННЯ ЗА ДОПОМОГОЮ ІНДЕКСУ

Потрібний для будь-якої сортування обмін значеннями деяких ЕОМ може тривати багато часу, якщо треба обмінюватися рядками або якщо кілька масивів розглядаються як один логічний елемент. Проте замість переупорядкування самих значень у процесі сортування можна утворити індекс (предметний покажчик), у якому відзначаються правильні місця значень масиві. Під час сортування значення залишаються на вихідних місцях, а змінюється індекс. Після закінчення сортування індекс використовується для копіювання значень, що сортуються, в новий масив або служить довідником для роботи з вихідним масивом.

Якщо нам потрібно відсортувати масив А(100) , то треба ввести індекс I(100) , найкраще цілий, якщо така можливість передбачена в системі (це скоротить пам'ять, що займає масивом), і задати початкові значення його елементів операторами

FOR L = 0 TO 100

Для індексу має виконуватись співвідношення 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 с: іл.