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.
Posortuj niemalejąco zbiór liczb całkowitych algorytmem sortowania szybkiego.
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.
Posortowany zbiór liczb całkowitych wypisany w jednym wierszu.
7 0 8 7 4 9
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)