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

Спробуйте відсортувати коробки: https://csfieldguide.org.nz/en/interactives/sorting-algorithms/

sorting.swf

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

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

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

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

Проходимо список стільки разів, скільки у ньому є елементів-1
Щоразу переглядаємо увесь список (крім останнього елемента) (можна до кінця відсортованої частини)
При потребі міняємо елементи місцями
for perebir in range(9):
    for nomer in range(9):
        if spysok[nomer]>spysok[nomer+1]:
            k=spysok[nomer]
            spysok[nomer]=spysok[nomer+1]
            spysok[nomer+1]=k
Інший запис:
spysok[nomer],spysok[nomer+1]=spysok[nomer+1],spysok[nomer]

Показати код/Сховати код^

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

Проходимо список стільки разів, скільки елементів-1
Щоразу знаходимо найменший елемент та його номер і міняємо його місцями з поточним
for perebir in range(9):
    print(spysok[perebir:10])
    fragment=spysok[perebir:10]
    m=fragment.index(min(fragment))
    k=m+perebir
    spysok[k],spysok[perebir]=spysok[perebir],spysok[k]
print(spysok)

Інший запис (без функцій min та index)
for n in range(10):
    m=spysok[n]
    for nomer in range(n,10):
        if m>=spysok[nomer ]:
            m=spysok[nomer ]
            a=nomer 
    k=spysok[n]
    spysok[n]=spysok[a]
    spysok[a]=k
print(spysok)

Показати код/Сховати код^

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

Проходимо список стільки разів, скільки елементів, починаючи з другого
Записуємо елемент у допоміжну змінну, і проходимо список у зворотньому напрямку, поки не знайдемо правильне місце для елемента. 
При цьому всі пройдені елементи зміщуються на 1
for perebir in range(10):
    j = perebir - 1
    element = spysok[perebir]
    del spysok[perebir]
    while (j >= 0) and (spysok[j] > element):
        j = j-1
    spysok.insert(j + 1, element)
print(spysok)

Інший спосіб (без функцій del та insert)
for n in range(1,10):
    a=n
    print(spysok[a])
    while (spysok[a] < spysok[a-1]) and (a=>0):
        k=spysok[a]
        spysok[a]=spysok[a-1]
        spysok[a-1]=k
        a-=1
print(spysok)

Показати код/Сховати код^

Задача 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://uk.wikipedia.org/wiki/Timsort

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

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

import random
spysok=[]
for nomer in range(10):
    k=(nomer//2)+1
    spysok.append(k)
print(spysok)

for nomer in range(10):
    k=random.randint(0,9)
    temp=spysok[nomer]
    spysok[nomer]=spysok[k]
    spysok[k]=temp
    print(spysok)

Показати код/Сховати код^

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

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

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

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

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

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

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

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