import numpy as np

def quicksort1(data, idx_start=None, idx_end=None): # rekurziv implementacio
    if idx_start is None:
        idx_start = 0
    if idx_end is None:
        idx_end = len(data) - 1
    # ha a feldolgozando resz nem tartalmaz legalabb ket elemet, akkor keszen vagyunk
    if idx_end <= idx_start:
        return
    # elemcserekkel particionaljuk a tombot
    mid = data[int((idx_start+idx_end)/2)]
    i = idx_start - 1
    j = idx_end + 1
    while True:
        while True:
            i += 1
            if data[i] >= mid:
                break
        while True:
            j -= 1
            if data[j] <= mid:
                break
        if i >= j:
            break
        data[i], data[j] = data[j], data[i]
    # rekurzivan rendezzuk az elso reszt
    quicksort1(data, idx_start, j)
    # rekurzivan rendezzuk a masodik reszt
    quicksort1(data, j+1, idx_end)


def quicksort2(data): # iterativ implementacio
    # egy veremben tartjuk nyilvan, hogy eppen melyik reszt dolgozzuk fel
    stack = []
    stack.append(0)
    stack.append(len(data)-1)
    # addig dolgozunk, amig van feldolgozando resz (nem ures a verem)
    while len(stack) > 0:
        idx_end = stack.pop()
        idx_start = stack.pop()
        # ha a feldolgozando resz nem tartalmaz legalabb ket elemet, akkor keszen vagyunk
        if idx_end <= idx_start:
            continue
        # elemcserekkel particionaljuk a tombot
        mid = data[int((idx_start+idx_end)/2)]
        i = idx_start - 1
        j = idx_end + 1
        while True:
            while True:
                i += 1
                if data[i] >= mid:
                    break
            while True:
                j -= 1
                if data[j] <= mid:
                    break
            if i >= j:
                break
            data[i], data[j] = data[j], data[i]
        # eloirjuk az elso resz rendezeset
        stack.append(idx_start)
        stack.append(j)
        # eloirjuk a masodik resz rendezeset
        stack.append(j+1)
        stack.append(idx_end)


def test(qsfunc, runs, datasize): # tesztrutin
    num_errors = 0
    for _ in range(runs):
        data = np.random.randint(low=-100, high=100, size=datasize)
        ref = np.sort(data)
        qsfunc(data)
        if any(data-ref):
            print('Hibasan rendezett tomb:', data)
            num_errors += 1
    if num_errors == 0:
        print(qsfunc.__name__ + ' test OK')


test(quicksort1, 1000, 100)
test(quicksort2, 1000, 100)