Упорядкування елементів у наборах даних допомагає швидше знаходити необхідні дані, виявляти закономірності і приймати обгрунтовані рішення.
Сортування вибором
Правило (ознака), за яким виконують впорядкування елементів, називають ключем впорядкування.
Ознакою впорядкування може бути: за зростанням (якщо значення елементів не повторюються), за неспаданням ( якщо значення елементів можуть повторюватися), за спаданням, за незростанням.
Метод сортування вибором полягає в пошуку на неопрацьованому зрізі списку мінімального значення і подальшому обміні цього значення з останнім елементом неопрацьованого зрізу. На наступному кроці неопрацьований зріз зменшується на один елемент.
Алгоритм сортування вибором мінімального елемента
Поки довжина неупорядкованої частини списку більше 1, повторювати:
- знайти в неупорядкованому зрізі списку мінімальне значення;
- поміняти місцями мінімальне значення з останнім елементом неупорядкованого зрізу;
- зменшити довжину неопрацьованого зрізу на один елемент.
На рис.1 жовтим кольором виділено найменший елемент серед елементів, що залишаються для перегляду на кожному кроці, стрілками — порядок обміну елементами.
Рис.1.
Реалізуємо алгоритм. Список arr заповнимо 10 випадковими числами.
| from random import randint | |
|
arr = []
for i in range(10):
arr.append(randint(1, 30))
|
# Заповнення списку
випадковими числами
|
|
print(arr)
|
# Виведення початкового списку |
| for k in range(len(arr)–1, 0, –1): |
# При кожній ітерації циклу
переглядається зріз [0: k+1]
|
| mk = min(arr[0: k+1]) |
# Знайшли мінімальний
елемент у зрізі arr[0: k+1]
|
| m = arr[0: k+1].index(mk) |
# Визначили індекс
мінімального елемента
|
| arr[k], arr[m] = arr[m], arr[k] |
# Мінімальний елемент
поміняли місцями з останнім у зрізі
|
| print(arr) | # Виведення упорядкованого списку |
Приклад:
Приклад виконання:
[21, 27, 15, 20, 1, 29, 12, 18, 26, 2]
[29, 27, 26, 21, 20, 18, 15, 12, 2, 1]
[21, 27, 15, 20, 1, 29, 12, 18, 26, 2]
[29, 27, 26, 21, 20, 18, 15, 12, 2, 1]
Впорядкування набору даних шляхом створення нового списку
Розглянемо алгоритм на прикладі, де а=[5, 1, 2, 4, 3] — вихідний список, а b — новий, упорядкований:
1. а=[5, 2, 4, 3] ; b=[1]
2. а=[5, 4, 3]; b=[1, 2]
3. а=[5, 4]; b=[1, 2, 3]
4. а=[5]; b=[1, 2, 3, 4]
5. а=[]; b=[1, 2, 3, 4, 5]
Програма (рис.2):
Рис.2Методи сортування
У мові Python для сортування списків використовують функцію sorted() та метод sort().
Різниця між sorted() і sort():
- sort() змінює сам список.
- sorted() створює новий відсортований список, не змінюючи вихідний.
Зверни увагу!
Для того, щоб використовувати метод sort(), елементи списку повинні мати однаковий тип.
За замовчуванням метод sort() сортує елементи списку за зростанням значень. Метод може змінити порядок сортування за допомогою параметрів:
- key — аргумент, який дає змогу визначити власну функцію порівняння при виклику методу sort();
- reverse — аргумент, який визначає порядок сортування. Якщо reverse=True, то елементи списку упорядковуються в порядку спадання (рис.3).
Рис.3
Результат:
Приклад використання ключа key
Маємо список S=['мама', 'тато', 'Оксана', 'Тарас'].
Відсортуємо список за зростанням та спаданням, використавши для порівняння функцію переведення символу з нижнього регістру до верхнього upper():
Для зміни порядку елементів списку на зворотній у вже відсортованому списку використовують метод reverse():
Результат виконання програми:
Джерела:
Інформатика : підруч. для 8 кл. закл. загал. серед. освіти / [Н.В.Морзе, О. В. Барна]. — Київ : УОВЦ «Оріон», 2025.