Przeczytaj
Implementacja algorytmu sortowania przez wstawianie w języku Python
Napisz program sortujący niemalejąco listę n liczb całkowitych. Wykorzystaj metodę sortowania przez wstawianie. Funkcja powinna sortować wejściową listę w miejscu. Przetestuj rozwiązanie dla danych:
Specyfikacja problemu:
Dane:
n– liczba naturalnaliczby– lista zawierającanliczb całkowitych do posortowania
Wynik:
Na standardowe wyjście wyświetlana jest posortowana niemalejąco tablica n-elementowa.
Porównaj swoje rozwiązanie z przedstawionym w prezentacji.
Porównania
Liczba potrzebnych porównań elementów listy może być wyrażona wzorami:
przypadek optymistycznyprzypadek optymistyczny: ,
przypadek pesymistycznyprzypadek pesymistyczny: .
Uwaga! Dwa porównania na początku pętli while liczymy jako jedno.
W tabeli przedstawiono porównania.
n | optymistyczna liczba porównań | pesymistyczna liczba porównań |
|---|---|---|
20 | 19 | 190 |
30 | 29 | 435 |
40 | 39 | 780 |
50 | 49 | 1225 |
60 | 59 | 1770 |
70 | 69 | 2415 |
80 | 79 | 3160 |
90 | 89 | 4005 |
100 | 99 | 4950 |
W tabeli przedstawiono przestawienia.
n | optymistyczna liczba przestawień | pesymistyczna liczba przestawień |
|---|---|---|
20 | 19 | 209 |
30 | 29 | 464 |
40 | 39 | 819 |
50 | 49 | 1247 |
60 | 59 | 1829 |
70 | 69 | 2484 |
80 | 79 | 3239 |
90 | 89 | 4094 |
100 | 99 | 5049 |
Słownik
przypadek, w którym podczas sortowania zostanie wykonana najmniejsza możliwa liczba operacji; lista uporządkowana w oczekiwanej kolejności – czyli dla sortowania w porządku rosnącym będzie to np. lista [2, 3, 4, 5]
przypadek, w którym podczas sortowania zostanie wykonana największa możliwa liczba operacji; lista uporządkowana w kolejności odwrotnej od oczekiwanej – czyli dla sortowania w porządku rosnącym będzie to np. lista [5, 4, 3, 2, 1]