"""
Térinformatikai algoritmusok
Rendezések
Máté Cserép <mcserep@inf.elte.hu>
"""

# Gyorsrendezés
def quickSort(array):
	n = len(array)
	_quickSort(array, 0, n - 1)

# Gyorsrendezés (résztömb)
def _quickSort(array, u, v):
	if u >= v:
		return;

	k = _partition(array, u, v)
	_quickSort(array, u, k - 1)
	_quickSort(array, k + 1, v)

# Segédalgoritmus: pivot elem helyrevitele (partícionálás)
def _partition(array, u, v):
	i = u + 1;
	j = v;
	while i <= j:
		while i <= v and array[i] <= array[u]:
			i += 1
		while j >= u + 1 and array[j] >= array[u]:
			j -= 1

		if i < j:
			_swap(array, i , j)
			i += 1
			j -= 1
	
	_swap(array, u, i - 1)
	return i - 1;

# Segédalgoritmus: elemcsere
def _swap(array, i, j):
	temp = array[i]
	array[i] = array[j]
	array[j] = temp
	

# Főprogram
array = [ 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 ];
print("Rendezetlen: {0}".format(array))
quickSort(array)
print("Rendezett: {0}".format(array))