Впорядкування вибором

Впорядкування вибором

Одним з важливих способів роботи з даними є сортування. Її використання не тільки прискорює, але й значно спрощує потрібний і важливий в області програмування процес. Вузький змив цього поняття в середовищі програмістів означає впорядкування записів у базі даних.


Методи сортування актуальні і донині, хоча технічний прогрес поповнився і сучасними способами роботи обчислювальної техніки. Відомий у своїй області вчений Д. Кнут стверджує, що майже половина часу в роботі над обробкою даних зайнята їх сортуванням. Він вказує три причини, які пояснюють такий хід речей:


  1. Сортування вибором та іншими способами застосовується дуже широко.
  2. Її алгоритм часто використовують без особливої на те потреби.
  3. Для вирішення поставлених завдань застосовується недосконала модель.

Для того щоб прискорити процес обробки даних, в першу чергу необхідно знайти рішення зазначених проблем. Програмісти намагаються створити таку структуру, яка сама б могла використовувати алгоритми, коли це потрібно. Якщо вона буде створена, то істотно прискориться робота з великим обсягом даних і відбудеться значна економія ресурсів обчислювальної техніки. Але поки цього не сталося, і ми розглянемо існуючі на сьогоднішній день методи сортування.

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

Сортування вибором, про яке піде мова, відноситься до внутрішньої. Саме на ній треба зупинитися більш детально, оскільки такий спосіб обробки дозволяє виконувати сортування більш гнучко і вигідно. Всі її методи діляться на 4 основні групи:

  1. Впорядкування вставок.
  2. Обробка даних підрахунком.
  3. Обмінний процес.
  4. Впорядкування вибором.

Потрібно зауважити, що чітких розмежувань між ними не існує, вони тісно переплітаються і дуже схожі між собою. Це обумовлює наявність певного зв 'язку в їх роботі. Найпростіший приклад роботи з обробкою даних дає сортування підрахунком. Вона є як би основою для інших, але на сьогоднішній день використовується вкрай рідко. Інший метод - вставки - вже більш важливий. Його ідея в тому, що конкретно розглянутий ключ поміщається на належне йому місце. Але тут є ряд незручностей і це негативно відбивається в роботі над великою кількістю записів. Багато вельми продуктивних методів обробки даних присутні в обмінному сортуванні. Найпопулярніший і найнаочніший у цій групі - так званий метод бульбашки. Робота в ньому будується на наступному алгоритмі: порівняння наступних один за одним записів виконується послідовно і, якщо значення першого з них більше, то вони просто міняються місцями. Такий процес йде до повного впорядкування.

І, нарешті, один з найважливіших, але і в той же час нескладних способів обробки баз даних - це сортування вибором. Як вже говорилося вище, вона відноситься до групи внутрішніх і на її основі можна з 'єднати кілька видів. Суть роботи методу - вибір, причому багаторазовий, одного елемента. Дії проводяться в такому порядку: вибирається найменший елемент зі списку, далі його надсилає в область виводу і заміна його значення на більше, ніж у всіх інших. Послідовність дій повторюється до повного вибору всіх даних списку.

Абсолютно ясно, що для реалізації алгоритму потрібна видимість всіх елементів і, крім того, області для виведення даних. І тут існує найбільш природний спосіб - це сортування простим вибором, тобто розбиття списку на кілька. При ньому слід вибрати найменший елемент масиву і обміняти його місцями з першим. Над тими елементами, які залишилися, знову виконуються такі маніпуляції до повної відповідності.