smuuf/primi

function qsort_wrapper(lst) {

    new = lst.copy()

    low = 0
    high = len(lst) - 1
    qsort(new, low, high)

    return new

}

function qsort(lst, low, high) {

    if (low < high) {
        pi = partition(lst, low, high)
        qsort(lst, low, pi - 1)
        qsort(lst, pi + 1, high)
    }

}

function partition(lst, low, high) {

    pivot = lst[high]
    i = (low - 1)
    j = low
    while (j <= high- 1) {
        if (lst[j] <= pivot) {
            i = i + 1
            tmp_a = lst[i]
            tmp_b = lst[j]
            lst[i] = tmp_b
            lst[j] = tmp_a
        }
        j = j + 1
    }

    tmp_a = lst[i + 1]
    tmp_b = lst[high]
    lst[i + 1] = tmp_b
    lst[high] = tmp_a

    return i + 1

}

a = [55,57,62,17,50,53,60,56,44,36,7,95,93,10,30,63,62,92,50,20,79,33,51,76,46,37,3,70,79,98,7,64,76,49,80,18,28,84,100,
    90,50,19,63,6,3,46,91,8,54,55,76,34,50,68,38,58,3,4,37,34,61,46,23,45,90,85,12,20,38,65,51,39,56,46,45,77,44,45,55,
    76,38,61,77,99,44,81,62,91,54,76,1,53,77,57,53,86,22,45,85,3]
new = qsort_wrapper(a)

expected = [1,3,3,3,3,4,6,7,7,8,10,12,17,18,19,20,20,22,23,28,30,33,34,34,36,37,37,38,38,38,39,44,44,44,45,45,45,45,46,
    46,46,46,49,50,50,50,50,51,51,53,53,53,54,54,55,55,55,56,56,57,57,58,60,61,61,62,62,62,63,63,64,65,68,70,76,76,76,
    76,76,77,77,77,79,79,80,81,84,85,85,86,90,90,91,91,92,93,95,98,99,100]

assert(new == expected)