Cvičení 8 – skupiny IB113/06,07
Řadící algoritmy
https://www.toptal.com/developers/sorting-algorithms
• Minipísemka (20 min)
• Pascalův trojúhelník pascal_triangle(N) dvěma způsoby:
◦ spočítat si n.tý řádek jako posloupnost kombinačních čísel (n nad 0, n nad 1, … , n
nad n - 1, n nad n) – dekompozice!
◦ druhá možnost: využívá seznamy, následující řádek vytvoří z aktuálního pomocí
pravidla o součtu dvou kombinačních čísel (n nad k) + (n nad k+1) = (n+1 nad k+1)
• Řazení:
https://www.fi.muni.cz/~xpelanek/IB113/sbirka/07-seznamy_algoritmy.html
1. Insert sort
2. Select sort
3. Bubble sort
• vlastní implementace
• průběžný výpis stavu seznamu
• počítejte průběžně počet přehození
• Jak se algoritmus chová na speciálních seznamech?
◦ Prázdný seznam: []
◦ Jednoprvkový seznam: [42]
◦ Už seřazený: [1, 2, 3, 3]
◦ Seznam stejných prvků: [2, 2, 2, 2]
• Chyby
• Pozměňte kód tak, aby nebyl změněn původní seznam, ale aby řadící
funkce vracela nový seznam.
• Porovnejte s vestavěným sortem (seznam s 5000 prvky)
from time import time (počet sekund od 1.1.1970 12am)