Сортування. Функції та методи



sorting.swf




15 алгоритмів сортування за 6 хвилин:


Бульбашкове сортування у танці:

"Веселкова візуалізація алгоритмів сортування": https://echo.lviv.ua/dev/6534


Задача 1. Сортування обміном. Метод "бульбашки”


Задача 2. Сортування вибором


Задача 3. Сортування вставкою


Задача 4. Визначити ефективність роботи алгоритмів сортування. Порахувати кількість порівнянь, виконаних у програмі. Порахувати кількість обмінів, виконаних у програмі


Задача 5. Відсортувати N чисел: http://dn.hoippo.km.ua:8889/problem/1114

Задача 6. Відсортувати методом "бульбашки", виводячи результат кожної ітерації: http://dn.hoippo.km.ua:8889/problem/1304

Задача 7. Відсортувати методом підрахунку: http://dn.hoippo.km.ua:8889/problem/1308 (https://uk.wikipedia.org/wiki/Сортування_підрахунком)


Функції та методи сортування

Функції та методи - це вбудовані команди (послідовності команд, підпрограми), котрі застосовуються до об'єктів основної програми. 

Функція - іменована послідовність команд, котра, як правило, має результат, котрий повертається в основну програму. Наприклад, sorted(spysok) . Функція має аргумент - назву списку, який пишеться в дужках. Функція повертає результат, але не змінює самого списку.

Метод - функція, котра використовується з об'єктами певного типу (класу). Першим формальним параметром є ім'я об'єкту. Наприклад, spysok.sort(). Метод застосовується до конкретного об'єкту (списку), і змінює його.

Наприклад, розглянемо початковий список

spysok=[1,5,2,8,4,0,6,8]

Якщо до цього списку застосуємо функцію sorted, то команда

print(sorted(spysok))

виведе впорядкований список. Але наступна команда 

print(spysok)

дозволяє переконатись, що сортування відбулось лише під час друку, сам список залишився незмінний. 

Якщо ж ми застосуємо метод sort(), то наступна команда друку дозволяє переконатись, що список тепер відсортовано.

spysok.sort()

print(spysok)

Щоб відсортувати у порядку спадання, можна вказати параметр reverse: 

spysok.sort(reverse=True) 

Для довідки: сортування у Python відбувається за алгоритмом Тімсорт: https://ru.wikipedia.org/wiki/Timsort


Перемішування

Задача. "Перемішати" елементи списку

Функція random.shuffle(spysok)


Задача. Надрукувати номери, під якими стояли елементи списку до сортування/перемішування.

Наприклад, список 5 3 2 8 1 після сортування виглядає 1 2 3 5 8. Номери цих елементів до сортування: 5 3 2 1 4


Задача. Після впорядкування списку визначити, скільки елементів послідовності залишились на своїх місцях після сортування/перемішування.


Пояснення сортування від учнів ліцею "Сихівський"

Сортування обміном:



Сортування вставкою



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



Остання зміна: понеділок 5 жовтня 2020 10:11