import random

#quick sort - sortowanie szybkie
#Rafal Gawlik
#ra.gawlik@gmail.com
#www.algorytm.org

#sortowanie
def quick_sort(L):  

	if len(L)<=1:  
		return L  

	#pobieranie pivota wg ktorego bedzimey operowac
	pivot=L[0]  
	less = []
	
	#wszystkie mniejsze elementy od pivot przerzucamy do listy mniejszych
	for x in L:
		if x<pivot:
			less.append(x)
	
	#wszystkie rowne elementy przerzucamy do listy rownych
	equal = []
	for x in L:
		if x==pivot:
			equal.append(x)

	#wszystkie wiesze elementy od pivot przerzucamy do listy wiekszych
	greater= []
	for x in L:
		if x>pivot:
			greater.append(x)

	#(rekurencja) odnawiamy procedure dla mniejszych i wiekszych elementow
	return quick_sort(less)+equal+quick_sort(greater)  

#generuje dane wejsciowe w porzadku malejacym
def malejaco(n):
	L = []
	for i in range(0,n):
		L.append(n-i-1)
	return L

#generuje dane wejsciowe w porzadku losowym
def losowe(n):
	L = []
	a = range(0,n)
	for i in range(0,n):
		L.append(random.choice(a))
	return L

#przyklad uzycia - pobierz dane od uzytkownika
n = input('Podaj ilosc danych: ')
w = input('Losowo/Malejaco [1/2]: ')

if int(w) == 1:
	L = losowe(int(n))
	print(L)
elif int(w) == 2:
	L = malejaco(int(n))
	print(L)
else:
	print('napisales bzdure')

L = quick_sort(L)

print('Po posortowaniu:')
print(L)