СОРТИРОВКА ТАБЛИЦІ покажчиків

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

Номер запису

Ключ

Інші поля

1

8

2

20

3

15

4

4

5

10

а б

Рис 91 Сортування записів: а вихідний файл б відсортований файл

Якщо обсяг даних в кожному записі файлу великий, то сортування самих записів є недоцільною, зокрема з причини великих тимчасових витрат на переміщення записів в процесі сортування Крім того, часто файл має не один, а кілька ключів У цьому випадку можна ввести допоміжну таблицю покажчиків або кілька таких таблиць і переміщати при сортування не записи, а покажчики на записи (рис 92) Таке сортування називаєтьсясортуванням таблиці адрес (ука зателей)У базах даних таблиця покажчиків може розміщуватися в окремому індексному файлі

Таблиця покажчиків може містити два поля: ключ і номер відповідного запису вихідного файлу

Рис 92 Відсортована таблиця покажчиків

При роботі з таблицями покажчиків завдання пошуку записи вирішується в два етапи:

1) у таблиці покажчиків шукається ключ 2) у файлі даних шукається запис (за її номером), з якою повязаний знайдений в таблиці покажчиків ключ

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

913 СОРТИРОВКА МАСИВУ методом бульбашки

Сортування методом бульбашки найбільш проста для реалізації, але має незначну обчислювальну ефективність

Не гаючи спільності, будемо для простоти викладу в подальшому розглядати завдання сортування масиву х цілих чисел, в якому першіп чисел повинні бути від-

сортовані так, щоб для

Ідея сортування методом бульбашки в тому, щоб переглянути масив последова

тельно кілька разів Один перегляд складається з порівняння кожного елемента масиву з наступним за ним елементом (xi   порівнюється зxi+1) Та обміну цих двох елементів, якщо вони розташовуються не в потрібному порядку (якщоxi&gt  х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  тільки п passTo є даний процес прискорюється з кожним переглядом

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

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

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

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

Якщо масив повністю відсортований, то обчислювальна складність методу складає 0 (п) необхідно л 1 порівнянь, щоб у цьому переконатися

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

Джерело: Бартеньев О В 1С: Підприємство: програмування для всіх Базові обєкти та розрахунки на одній дискеті М: Діалог-МІФІ, 2005 464 с

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


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

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

Ваш отзыв

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

*

*