1def partition(items, lo, hi)
 2  pos = ((hi-lo)/2) + lo
 3  pivot = items[pos]
 4  i = lo
 5  items[hi], items[pos] = items[pos], items[hi]
 6  for j in lo..hi
 7    puts [items[j], pivot].inspect
 8    if items[j] < pivot
 9      items[i], items[j] = items[j], items[i]
10      i+=1
11    end
12    puts [pivot, items].inspect
13  end
14  items[i], items[hi] = items[hi], items[i]
15  puts [pivot, items].inspect
16  i
17end
18
19def quicksort(items, lo, hi)
20  if lo < hi
21    p = partition(items, lo, hi)
22    quicksort(items, lo, p - 1)
23    quicksort(items, p + 1, hi)
24  end
25end
26
27puts "Sorting"
28puts [6, 8, 4, 5, 3, 1, 7].inspect
29
30puts "quick sort"
31quicksort([6, 8, 4, 5, 3, 1, 7], 0, 6)