того щоб зрозуміти важливість перегрупування елементів з однаковими ключами сортування, уявімо базу даних, яка впорядкована за основним ключу і додатковому ключу. p align="justify"> Наприклад, список поштових відправлень з поштовим індексом в якості основного ключа і прізвищем в якості додаткового ключа в рамках одного поштового індексу.
Коли новий адресу додається в список і список знову сортується, вам не потрібно перестановка додаткових ключів. Для забезпечення цього сортування не повинна виконувати операції обміну для основних ключів з однаковими значеннями. br/>
2.3 Постановка задачі сортування і методи її вирішення
Задачу сортування даних можна сформулювати для інформаційної сукупності самої різної природи - для числової інформації, для слів і символів тексту. Для цього, потрібно визначити поняття порядку для елементів масиву, визначити поняття "більше" і "менше" для кожної пари елементів. Відсортувати послідовність чисел можна точно таким же способом, як і послідовність рядків тексту. Необхідно тільки визначити який з елементів пари "більше" іншого. p align="justify"> Більш важливим для вибору алгоритму є місце розташування даних - в оперативній пам'яті комп'ютера або на зовнішньому пристрої.
Тут грає роль відмінність в основних критеріях якості - для даних в оперативній пам'яті основними позитивними властивостями методу є швидкодія і потреби в додатковій пам'яті. Для дискових файлів дуже важливим показником є ​​кількість звернень до пристрою для виконання операцій введення-виведення - воно має бути мінімальним. p align="justify"> Розрізняють два види сортування даних:
сортування даних, розташованих в оперативній пам'яті комп'ютера (внутрішня сортування);
сортування даних, розташованих на зовнішніх запам'ятовуючих пристроях (зовнішня сортування).
Сформулюємо постановку задачі сортування даних для внутрішнього сортування одновимірного числового масиву за зростанням.
Мається одновимірний масив чисел, що складається з n елементів: X [n]. Переставити елементи масиву так, щоб їх значення розташовувалися в порядку зростання. Іншими словами, для будь-якої пари елементів X [i] і X [i +1] виконується нерівність виду:
[i] <= X [i +1].
У цій задачі однозначно визначається структура даних для внутрішнього сортування (одновимірний масив) та порядок упорядкування елементів. Ключем для визначення порядку елементів є само числове значення елемента масиву. Результатом розв'язання задачі має бути програма сортування масиву одним або кількома методами. p align="justify"> При розробці програми можна скористатися різними алгоритмами. Найбільш відомими є наступні:
метод сортування обмінами ("бульбашкова" сортування);
...
