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