НОУ ІНТУІТ, Лекція, Одномірні масиви задачі сортувань елементів масиву
Сортування методом простого вибору (простий перебір)
Це найприродніший алгоритм упорядкування. При даному сортуванні з масиву вибирається елемент із найменшим значенням та обмінюється з першим елементом. Потім з n - 1 елементів, що залишилися, знову вибирається елемент з найменшим ключем і обмінюється з другим елементом, і т.д. (рис. 12.2)
- знаходимо мінімальне значення у поточній частині масиву;
- здійснюємо обмін цього значення зі значенням на першій невідсортованій позиції;
- далі сортуємо хвіст масиву, виключивши з розгляду відсортовані елементи.
Як і у бульбашковому сортуванні, зовнішній цикл виконується n-1 разів, а внутрішній – у середньому n/2 разів. Отже, сортування методом простого вибору вимагає
Сортування методом простого включення (зсув-вставка, вставками, вставка та зсув)
Хоча цей метод сортування набагато менш ефективний, ніж складні алгоритми (такі як швидке сортування), він має ряд переваг:
- простий у реалізації;
- ефективний на невеликих наборах даних, на наборах даних до десятків елементів може бути кращим;
- ефективний на наборах даних, які вже частково відсортовані;
- це стійкий алгоритм сортування (не змінює порядок елементів, які вже відсортовані);
- може сортувати масив у міру його одержання;
- не потребує тимчасової пам'яті, навіть під стек.
На кожному кроці алгоритму вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію вже відсортованої послідовності доти, поки набір вхідних даних не буде вичерпаний. Метод вибору чергового елемента з вихідного масивудовільний; може використовуватися практично будь-який алгоритм вибору (рис. 12.3).
На відміну від бульбашкового сортування та сортування простого вибору, кількість порівнянь у сортуванні вставками залежить від початкової впорядкованості списку. Якщо список вже відсортований, кількість порівнянь дорівнює n-1; інакше його продуктивність є величиною порядку n 2 .
Ключові терміни
Ключ сортування- це частина даних, що визначає порядок елементів.
Сортування– це впорядкування набору однотипних даних щодо зростання або спадання.
Сортування методом "бульбашка"- це алгоритм попарного порівняння елементів одновимірного масиву.
Сортування методом простого включення– це алгоритм послідовного поміщення елемента масиву у відсортовану частину відповідно до ключа сортування.
Сортування методом простого вибору– це алгоритм послідовного обміну мінімального та першого елементів невідсортованої частини масиву.