我试图在ruby中实现快速排序,但是在第一个pivot分区之后陷入了如何以递归方式调用的问题.请帮助我了解如何继续,并让我知道我的编码风格到目前为止是否良好.
class QuickSort
$array= Array.new()
$count=0
def add(val) #adding values to sort
i=0
while val != '000'.to_i
$array[i]= val.to_i
i=i+1
val = gets.to_i
end
end
def firstsort_aka_divide(val1,val2,val3) #first partition
$count = $count+1
@pivot = val1
@left = val2
@right =val3
while @left!=@right do # first divide/ partition logic
if $array[@right] > $array[@pivot] then
@right= @right-1
elsif $array[@right] < $array[@pivot] then
@var = $array[@right]
$array[@right] = $array[@pivot]
$array[@pivot] = @var
@pivot = @right
@left = @left+1
end
if $array[@left] < $array[@pivot]
@left= @left+1
elsif $array[@left] > $array[@pivot]
@var = $array[@left]
$array[@left] = $array[@pivot]
$array[@pivot] = @var
@pivot =@left
end
end
puts "\n" # printing after the first partition i.e divide
print " Array for for divide ---> #{$array}"
puts "\n"
puts " pivot,left,right after first divide --> #{@pivot},#{@left},#{@right}"
firstsort_aka_divide() # Have to call left side of partition recursively -- need help
firstsort_aka_divide() # Have to call right side of partition recursively -- need help
end
end
ob= QuickSort.new
puts " Enter the numbers you want to sort. \n Press '000' once you are done entering the values"
val = gets.to_i
ob.add(val)
puts " Sorting your list ..."
sleep(2)
ob.firstsort_aka_divide(0,($array.size-1)) # base condition for partitioning
解决方法
这是一个基于
Wikipedia’s simple-quicksort pseudocode的(非常)天真的快速实施方案：
def quicksort(array) #takes an array of integers as an argument
您需要一个基本案例,否则您的递归调用永远不会终止
if array.length <= 1 return array
现在选择一个支点：
else
pivot = array.sample
array.delete_at(array.index(pivot)) # remove the pivot
#puts "Picked pivot of: #{pivot}"
less = []
greater = []
循环遍历数组,将项目与pivot进行比较,并将它们收集到越来越多的数组中.
array.each do |x|
if x <= pivot
less << x
else
greater << x
end
end
现在,递归地在越来越少的数组上调用quicksort().
sorted_array = [] sorted_array << self.quicksort(less) sorted_array << pivot sorted_array << self.quicksort(greater)
返回sorted_array,你就完成了.
# using Array.flatten to remove subarrays sorted_array.flatten!
你可以测试一下
qs = QuickSort.new puts qs.quicksort([1,2,3,4,5]) == [1,5] # true puts qs.quicksort([5]) == [5] # true puts qs.quicksort([5,-5,11,3]) == [-5,5,11] # true puts qs.quicksort([5,3]) == [5,3] # false