Алгоритм сортування

Електрична табулююча система, створена Германом Голлерітом для автоматичного сортування інформації

Алгори́тм сортува́ння — в інформатиці — процес, що впорядковує множину однотипних елементів за певною ознакою (ключем сортування). Сортування є типовою проблемою обробки даних, що забезпечує розміщення елементів невпорядкованого набору значень в порядку монотонного зростання або спадання значення ключа.

Історична довідка

Потреба у створенні швидких та ефективних алгоритмів сортування вперше виникла в середині 20 ст. у США і була зумовлена великими обсягами інформації, яку потрібно було впорядковувати — результатами перепису населення. Устаткування для цього запропонував Г. Голлеріт, створивши електромеханічний пристрій для автоматичного оброблення інформації, записаної на перфокартах, — так звану електричну табулюючу систему Голлеріта (англ. Hollerith Electric Tabulating System). Ці перфокарти можна було сортувати відповідно до перфорації.

Наступний етап (з початку 1940-х) пов’язаний з появою перших електронних обчислювальних машин (ЕОМ) та позначається потребою у зменшенні часу сортування великих масивів даних. Першою програмою для обчислювальних машин стала саме програма сортування. У 1945 Дж. фон Нейманн (США) для тестування набору команд одного з перших електронних комп’ютерів EDVAC (скор. від англ. Electronic Discrete Variable Automatic Computer) розробив програми сортування методом злиття. У 1946 опублікована перша стаття про алгоритми сортування одного з розробників першого програмованого комп’ютера ENIAC (скор. від англ. Electronic Numerical Integrator and Computer) Дж. В. Моклі «Про сортування та злиття». Перехід до сортування даних за допомогою ЕОМ викликав поділ сортування на зовнішнє (обробка даних з периферійних пристроїв) і внутрішнє (обробка даних із внутрішньої пам’яті ЕОМ).

До середини 1950-х найпоширенішими були модифікації сортування злиттям і вставками; надалі розвиток ЕОМ другого покоління став передумовою до появи перших мов програмування високого рівня (Фортран, Алгол, Кобол), придатних для реалізації різноманітних алгоритмів, і значно ширшого застосування комп’ютерів у результаті зменшення їх габаритів і вартості. У цей час були розроблені такі алгоритми: швидке сортування (англ. Quick Sort) — Ч. Е. Хоар (Велика Британія), сортування з регресним кроком (англ. Hell Sort) — Д. Л. Шелл (США), пірамідальне сортування (англ. Heap Sort) — Дж. В. Вільямс (Велика Британія) тощо. Ці алгоритми широко використовуються й донині.

Інтенсивного розвитку теорія сортування зазнала наприкінці 1960-х. Алгоритми, що з’явилися пізніше, багато в чому були варіаціями вже відомих методів. Набули поширення адаптивні методи сортування, орієнтовані на швидше виконання у випадках, коли вхідна послідовність відповідає заздалегідь визначеним критеріям. Результати цього етапу розвитку алгоритмів сортування відображено в фундаментальній монографії «Мистецтво програмування» (англ. «The Art of Computer Programming») Д. Е. Кнута (1973, США).

До початку 1970-х були поширені такі алгоритми: сортування за допомогою підрахунку; сортування шляхом вставок; обмінне сортування; сортування за допомогою вибору; сортування методом злиття; сортування методом розподілу. Період із середини 1970-х до 1990-х відзначився досягненнями значних успіхів у збільшенні швидкості сортування за рахунок підвищення ефективності існуючих алгоритмів шляхом їхньої доробки чи комбінування. Наприклад, Е. В. Дейкстра (Нідерланди) у 1981 запропонував алгоритм плавного сортування (англ. Smooth Sort), що є розвитком пірамідального сортування.

Основні характеристики

час, необхідний на впорядкування множини з n елементів;
обсяг оперативної пам’яті для виконання сортування;
стабільність: чи змінює сортування взаємне розташування елементів із однаковими ключами.

Часова складність алгоритмів сортування різниться від O(n ) до O(n²).

Приклади алгоритмів сортування з часовою складністю O(n²): сортування вставкою (англ. Insertion Sort), сортування вибором (англ. Selection Sort ), бульбашкове сортування (англ. Bubble Sort ).

Приклади алгоритмів сортування з часовою складністю O(n log n): сортування злиттям, швидке сортування, пірамідальне сортування. Але стабільні алгоритми сортування, що працюють за час O(n log n), потребують O(n) додаткової пам'яті.

Приклади алгоритмів сортування з часовою складністю O(n): cортування комірками, cортування підрахунком, cортування за розрядами. Такі алгоритми потребують використання додаткової інформації про елементи.

На практиці елементи множини, що впорядковуються, містять не тільки ключ сортування, але й іншу інформацію. Обсяг цієї інформації може бути значно більшим за обсяг самого ключа (наприклад, ключ — ім’я файлу, а супутня інформація — вміст цього файлу). Тому важливо, щоб впорядкування відбувалось не у самому масиві елементів, а в масиві ключів, що є вказівниками на інші дані.

Приклади

Схема бульбашкового сортування

Сортування вставками — елементи вхідної послідовності проглядаються по одному, і кожен новий елемент, що надійшов, розміщується в придатне місце серед раніше упорядкованих елементів. Застосовується для майже цілком відсортованих даних та даних невеликого розміру. Часова складність — O(n²).
Бульбашкове сортування — у вхідній послідовності порівнюються два сусідні елементи і, якщо вони не відповідають критерію сортування, ці елементи міняються місцями. Алгоритм працює доти, доки весь масив даних не буде впорядковано. Часова складність — O(n²).
Сортування вибором — поєднання бульбашкового сортування та сортування вставками. Як і у бульбашкового сортування, цей алгоритм проходить масивом раз за разом, переміщаючи одне значення на правильну позицію. Однак, на відміну від бульбашкового сортування, вибирає найменше невідсортоване значення замість найбільшого. Як і при сортуванні вставками, упорядкована частина масиву розташована на початку, тоді як у бульбашкового сортування — наприкінці. Часова складність — O(n²).
Швидке сортування — алгоритм, який не потребує додаткової пам’яті, оскільки використовує прості цикли й операції, працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. З масиву обирається опорний елемент, і весь масив розбивається на дві частини: в першій — елементи, не більші даного, в другій — не менші. Впорядкування кожної з частин відбувається рекурсивно. Час роботи алгоритму сортування залежить від того, який елемент обрано як опорний. У найгіршому випадку час роботи алгоритму — O(n²), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n).
Сортування Шелла — удосконалений варіант сортування включенням. Ідея методу Шелла полягає в порівнянні елементів, розташованих не тільки поруч, а й на певній відстані один від одного. Сортування Шелла не є стабільним.

Застосування

Сортування — невід’ємна частина роботи практично з будь-яким видом інформації, що забезпечує її класифікацію й аналіз. Часова складність алгоритмів сортування та обсяг пам’яті, що використовується для сортування, значно впливають на ефективність комп’ютерної обробки даних. Велике значення має масштабованість цих алгоритмів, можливість їх застосування для обробки великих даних (англ. Big Data), придатність для впорядкування складних інформаційних структур. Наприклад, призначення інформаційно-пошукових систем полягає не стільки в їх здатності знайти релевантний документ серед доступних веб-сторінок, скільки в умінні ефективно сортувати ці веб-сторінки, знаходячи ті, які задовільнять персональні інформаційні потреби конкретного користувача.

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

Українські розробки

Українські науковці багато років займаються вдосконаленням та застосуванням алгоритмів сортування для оптимізації обчислень. Перші такі дослідження пов’язані з розробкою першої вітчизняної ЕОМ — МЕСМ (пристосування сортування з перфокартами для введення вихідних даних у машину). Проблемами сортування інформації займалися дослідники Інституту кібернетики імені В. М. Глушкова НАН України для організації обчислень на комп’ютерах із розподіленою пам’яттю. Ці дослідження стосувалися як фундаментальних досліджень символьної обробки інформації, так і їхнього практичного застосування (в паралельних обчисленнях, розпізнаванні образів, нейронних мережах, хмарних обчисленнях).

Література

Цейтлин Г. Е. Поиск и сортировка: классификация, трансформация, синтез. II // Автоматика и телемеханика. Москва : Наука, 1992. №5. С.156–165. URL: http://www.mathnet.ru/links/604dedb15d6dd8201f745966ab2117cd/at3305.pdf
Кнут Д. Э. Искусство программирования : в 4 т. / Пер. с англ. М. Р. Саит-Аметовой. 2-е изд. Киев : Вильямс, 2007. Том 3: Сортировка и поиск. 832 с.
Ткачов В. В., Огєєнко П. Ю., Макітренко Р. В. Комп'ютерні технології та програмування : в 2 т. Донецьк : Національний гірничий університет, 2011. Т. 2. 179 с. URL:
http://ir.nmu.org.ua/bitstream/handle/123456789/2719/НТБ453510.pdf?sequence=1&isAllowed=y
Мельничук А. С. та ін. Аналіз методів сортування масиву чисел // Технологический аудит и резервы производства. 2013. № 4/1(12). С. 37–40.
Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона / Пер. с англ. Ф. В. Ткачёв. 2-е изд., испр. Москва : ДМК Пресс, 2016. 272 с.
Грехов А. М. Інтелектуальні інформаційні технології в бізнесі. Дюссерльдорф : Lambert, 2018, 335 с.

Автор ВУЕ

Ю. В. Рогушина

Покликання на цю статтю: Рогушина Ю. В. Алгоритм сортування // Велика українська енциклопедія. URL: https://vue.gov.ua/Алгоритм сортування (дата звернення: 6.05.2024).

Статус гасла: Оприлюднено
Оприлюднено: 26.12.2017

Важливо!

Ворог не зупиняється у гібридній війні і постійно атакує наш інформаційний простір фейками.

Ми закликаємо послуговуватися інформацією лише з офіційних сторінок органів влади.

Збережіть собі офіційні сторінки Національної поліції України та обласних управлінь поліції, аби оперативно отримувати правдиву інформацію.

Отримуйте інформацію тільки з офіційних сайтів

Алгоритм сортування

Зміст

Історична довідка

Основні характеристики

Приклади

Застосування

Українські розробки

Література

Автор ВУЕ

Важливо!

Офіс Президента України

Верховна Рада України

Кабінет Міністрів України

Служба безпеки України

Міністерство оборони України

Міністерство внутрішніх справ України

Генеральний штаб Збройних сил України

Державна прикордонна служба України

Кіберполіція

Національна поліція України