Sortowanie szybkie w Pythonie

powrót

Algorytm został opisany w tym miejscu.

Algorytm sortowania szybkiego, znany również jako Quicksort, jest efektywnym algorytmem, który działa na zasadzie dziel i zwyciężaj.

Najważniejsze cechy algorytmu:

• algorytm wykorzystuje technikę dziel i zwyciężaj,
• złożoność algorytmu jest rzędu $$O(n\log n),$$
• algorytm jest niestabilny (może zmieniać pierwotne położenie względem siebie elementów o tych samych wartościach),
• algorytm sortuje w miejscu (nie potrzebuje dodatkowej tablicy do uporządkowania danych.

Zadanie

Posortuj niemalejąco zbiór liczb całkowitych algorytmem sortowania szybkiego.

Wejście

W pierwszym wierszu pewna ilość liczb całkowitych. Ilość liczb jest nie większa niż milion oraz moduł każdej z nich jest nie większy niż miliard.

Wyjście

Posortowany zbiór liczb całkowitych wypisany w jednym wierszu.

Przykład

Wejście:

7 0 8 7 4 9

Wyjście:

0 4 7 7 8 9

#*****************www.algorytm.edu.pl****************
def quick_sort(lista, lewy, prawy):
    if lewy < prawy:
        i = lewy
        j = prawy

        # wybieramy punkt odniesienia
        pivot = lista[(lewy + prawy) // 2]
        while True:
            # szukam elementu wiekszego lub rownego piwot stojacego
            # po prawej stronie wartosci pivot
            while pivot > lista[i]:
                i+=1

            # szukam elementu mniejszego lub rownego pivot stojacego
            # po lewej stronie wartosci pivot
            while pivot < lista[j]:
                j -= 1

            if i <= j:
                # funkcja swap zamienia wartosciami tab[i] z tab[j]
                lista[i], lista[j] = lista[j], lista[i]
                i+=1
                j-=1
            else:
                break

        # jesli liczniki sie nie minely to zamień elementy ze soba
        # stojace po niewlasciwej stronie elementu pivot
        if j > lewy:
            quick_sort(lista, lewy, j)
        if i < prawy:
            quick_sort(lista, i, prawy)

lista = list(map(int, input().split()))
quick_sort(lista, 0, len(lista) - 1)
print(*lista)