#/***********************************************************
#    qsort1.rb -- クイックソート
#***********************************************************/

def quicksort(a,  first,  last)
    x = a[(first + last) / 2]
    i = first;  j = last
    while (true) 
        while (a[i] < x); i += 1; end
        while (x < a[j]); j -= 1; end
        if (i >= j); break; end
        t = a[i];  a[i] = a[j];  a[j] = t
        i += 1;  j -= 1
    end
    if (first  < i - 1); quicksort(a, first , i - 1); end
    if (j + 1 < last); quicksort(a, j + 1, last); end
end

N = 20
a = []

printf("Before:")
for i in 0...N
    a[i] = (rand * 100 + 1).to_i
    printf(" %2d", a[i])
end
printf("\n")
quicksort(a, 0, N - 1)
printf("After: ")
for i in 0...N; printf(" %2d", a[i]); end
printf("\n")

exit 0