Сортування вибором

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

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

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

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

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

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

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

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

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

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