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