Niech lista $L = [l_1, \ldots, l_n]$.

1) Para $(l_k, l_m)$ jest inwersją, jeśli $k<m$, ale $l_k>l_m$. Napisz program, który dla zadanej listy różnych elementów, zwróci listę par wszystkich inwersji w tej liście.

Przykładowo, jeśli lista to $L = [1, 5, 2, -1]$, inwersje na tej liście, to: $[(1, -1), (5, 2), (5, -1), (2, -1)]$.

2) Rangą elementu $l_i$ jest jego indeks w posortowanej liście. Napisz program, który dla zadanej listy różnych elementów, zwróci listę rang poszczególnych elementów.

Przykładowo, jeśli lista to $L = [1, 5, 2, -1]$, po posortowaniu otrzymujemy listę $S = [-1, 1, 2, 5]$. Wobec tego liczbie $1$ odpowiada ranga $1$ (druga na posortowanej liście), liczbie $5$ ranga $3$ (ostatnia na posortowanej liście), liczbie $2$ odpowiada ranga $2$, liczbie $-1$ odpowiada ranga $0$. Oznacza to, że lista rang elementów listy $L$ to $R = [1, 3, 2, 0]$.

Sortowanie przez zliczanie (counting sort) jest algorytmem służącym do sortowania list złożonych z elementów mogących przyjmować wartości z jakiegoś skończonego, posortowanego zestawu (np. liczby naturalne z zakresu od 1 do 10). Polega on na zliczaniu wystąpień każdej wartości z zakresu w danej liście i następnie w oparciu o tę wiedzę budowaniu listy posortowanej.

Załóżmy, że mamy listę lista, której elementy przyjmują wartości z posortowanej listy klucze. Algorytm przebiega następująco:

1. Dla każdego elementu listy klucze obliczamy liczbę wystąpień tego elementu w liście lista.
2. Otrzymujemy słownik wystapienia, którego kluczami są elementy listy klucze a wartościami liczba wystąpień każdego klucza w liście lista. Na podstawie słownika wystapienia możemy określić ile razy i na jakich miejscach w posortowanej liście pojawią się poszczególne klucze.
3. Tworzymy słownik pozycje o kluczach z listy klucze i wartościach będących pierwszymi wystąpieniami danego klucza w posortowanej liście (wartość dla każdego klucza jest równa sumie wartości dla wszystkich kluczy go poprzedzających).
4. Tworzymy pustą listę posortowana o tej samej długości co lista Iterując się po elementach elem oryginalnej listy lista, wpisujemy każdy element w miejscu o indeksie równym wystapienia[elem] i zwiększamy wystapienia[elem] o 1.

Przykładowo, jeżeli mamy listę lista=[9,7,7,1,1,7,8] i klucze=range(1,10), to otrzymujemy słownik wystapienia={1:2,7:3,8:1,9:1}.

Modyfikujemy słownik wg punktu 3. otrzymując pozycje={1:0,7:2,8:5,9:6}

Tworzymy listę posortowana o długości 7 (np. listę samych zer).

Iterujemy się po elementach listy lista:

• Dla lista[0]==9 mamy pozycje[9]==6 zatem posortowana[6]=9 i wykonujemy pozycje[9]+=1
• Dla lista[1]==7 mamy pozycje[7]==2 zatem posortowana[2]=7 i wykonujemy pozycje[7]+=1
• Dla lista[2]==7 mamy już teraz pozycje[7]==3 zatem posortowana[3]=7 i wykonujemy pozycje[7]+=1
• itd.

W efekcie wypełniamy całą listę posortowana==[1, 1, 7, 7, 7, 8, 9].

1) Uzasadnij, dlaczego tak zapisany algorytm działa w czasie proporcjonalnym do liczby elementów w liście i jest algorytmem stabilnym.

2) Napisz funkcję sortowanie_zliczanie(lista, klucze), która posortuje listę lista o elementach przyjmujących wartości z listy klucze za pomocą podanego algorytmu. Postaraj się, aby napisana funkcja miała optymalną złożoność obliczeniową (na przykład używanie metody .count() z osobna dla każdego klucza nie jest optymalne). Możesz założyć, że podana przez użytkownika lista lista zawiera wyłącznie elementy o wartościach z listy klucze.

3) Wygeneruj listę 1000 losowo wybranych liczb naturalnych z przedziału od 0 do 9 (wykorzystaj funkcję choice() z biblioteki random). Porównaj czas działania napisanej funkcji sortowanie_zliczanie() na wygenerowanej liście dla listy kluczy list(range(10)) z innymi znanymi ci z wykładu algorytmami sortowania.

Możesz skorzystać z kodów do sortowania:

def sortowanie_bąbelkowe(lista, relacja=lambda x, y: x <= y):
    n = len(lista)
    dalej = True
    i = 0
    while dalej:
        dalej = False
        for j in range(n-1-i):
            if not relacja(lista[j],lista[j+1]):
                lista[j], lista[j+1] = lista[j+1], lista[j]
                dalej = True
        i += 1
 
def sortowanie_wstawianie(lista, relacja=lambda x, y: x <= y):
    for i in range(1, len(lista)):
        li = lista[i]
        j = i
        while j>0 and not relacja(lista[j-1], li):
            lista[j] = lista[j-1]
            j -= 1
        lista[j] = li
 
def sortowanie_wybieranie(lista, relacja=lambda x, y: x <= y):
    n = len(lista)
    for i in range(n-1):
        j = i
        for k in range(i+1, n):
            if not relacja(lista[j], lista[k]):
                j = k
        if j != i:
            lista[i], lista[j] = lista[j], lista[i]
 
def sortowanie_scalanie(lista, relacja=lambda x, y: x <= y):
    def scal(lista1, lista2):
        wynik = []
        n1 = len(lista1)
        n2 = len(lista2)
        i1 = 0
        i2 = 0
        while i1 < n1 and i2 < n2:
            if relacja(lista1[i1], lista2[i2]):
                wynik.append(lista1[i1])
                i1 += 1
            else:
                wynik.append(lista2[i2])
                i2 += 1
        return wynik + lista1[i1:] + lista2[i2:]
    n = len(lista)
    if n <= 1:
        return lista.copy()
    k = n//2
    l1, l2 = lista[:k], lista[k:]
    l1 = sortowanie_scalanie(l1)
    l2 = sortowanie_scalanie(l2)
    return scal(l1, l2)

oraz pomiaru czasu:

from random import seed, randrange, setstate, getstate, shuffle
from time import perf_counter
from itertools import repeat
import gc
 
def zmierz_raz_sortowanie(algorytm, lista, min_time=0.2):
    czas = 0
    ile_teraz = 1
    stan_gc = gc.isenabled()
    gc.disable()
    while czas < min_time:
        kopie_list = [lista.copy() for _ in repeat(None, ile_teraz)]
        if ile_teraz == 1:
            start = perf_counter()
            algorytm(kopie_list.pop())
            stop = perf_counter()
        else:
            iterator = repeat(None, ile_teraz)
            start = perf_counter()
            for _ in iterator:
                algorytm(kopie_list.pop())
            stop = perf_counter()
        czas = stop-start
        ile_teraz *= 2
    if stan_gc:
        gc.enable()
    return czas/ile_teraz
 
 
def zmierz_min_sortowanie(algorytm, lista, serie_min=5, min_time=0.2):
    pomiary = []
    generator = getstate()
    seed()
    my_seed = randrange(1000)
    for _ in repeat(None, serie_min):
        seed(my_seed)
        pomiary.append(zmierz_raz_sortowanie(algorytm, lista, min_time=min_time))
    setstate(generator)
    return min(pomiary)
 
def zmierz_sortowanie(algorytm, lista, serie_median=10, serie_min=5, min_time=0.2):
    pomiary = []
    lista = lista.copy()
    for _ in repeat(None, serie_median):
        shuffle(lista)
        pomiary.append(zmierz_min_sortowanie(algorytm, lista, serie_min=serie_min, min_time=min_time))
    pomiary.sort()
    if serie_median%2==0:
        return (pomiary[serie_median//2-1]+pomiary[serie_median//2])/2
    else:
        return pomiary[serie_median//2]

Przykład użycia pomiaru czasu dla algorytmu sortowania:

zmierz_sortowanie(lambda lista: lista.sort(), list(range(1000)))

Porównaj kod do mierzenia czasu funkcji znany z wcześniejszych wykładów z kodem powyżej. Jakie zmiany wprowadzono? Zastanów się, dlaczego są one konieczne do prawidłowego pomiaru czasu algorytmu sortowania (lub innego algorytmu modyfikującego listę w miejscu).

Sortowanie pozycyjne (radix sort) jest algorytmem sortowania list liczb wymiernych, poprzez iteracyjne sortowanie ich na podstawie ich kolejnych cyfr.

Zmodyfikuj napisaną w zadaniu 2 funkcję sortowanie_zliczanie(lista, klucze=list(range(10))) tak, aby sortowała listę liczb naturalnych na podstawie $k$-tej cyfry znaczącej. Użyj jej do napisania funkcji sortowanie_pozycyjne(lista), która posortuje listę lista zawierającą liczby naturalne na podstawie kolejnych cyfr znaczących (zaczynając od cyfry jedności) zmodyfikowaną metodą sortowania przez zliczanie, aż do wyczerpania się cyfr znaczących (np. kiedy największa liczba na liście jest 5-cyfrowa, to powinno zostać wykonane 5 sortowań po każdej cyfrze znaczącej).