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

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

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

FOR L = 0 TO 100

I(L) =L NEXT L

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

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

При введенні індексу програма для сортування методом бульбашки з підрозд 451 перетвориться на наступну програму:

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

роздрукують відсортований набір значень

Застосування індексу дає велику перевагу в разі, коли значення даних розподілені по декількох масивів Якщо, скажімо, упорядковано значення масивів А (10), В (9), С (27), то можна створити індекс I (46), в якому перші 10 елементів вказують на масив А, наступні 9 – на масив В, а останні 27 – на С Звичайно, алгоритм треба модифікувати так, щоб у порівняннях могли брати участь як елементи масиву А, так і елементи масивів В і С

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

Джерело: Уолш Б Програмування на Бейсике: Пер з англ М: Радіо і звязок, 1988 336 с: ил

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*