我正在尝试在 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,0,($array.size-1)) # base condition for partitioning
最佳答案
这就是我在 Ruby 中实现快速排序的方式:
def quicksort(*ary)
return [] if ary.empty?
pivot = ary.delete_at(rand(ary.size))
left, right = ary.partition(&pivot.method(:>))
return *quicksort(*left), pivot, *quicksort(*right)
end
实际上,我可能会让它成为 Array
的实例方法:
class Array
def quicksort
return [] if empty?
pivot = delete_at(rand(size))
left, right = partition(&pivot.method(:>))
return *left.quicksort, pivot, *right.quicksort
end
end
关于ruby - Ruby 语言中的快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21371681/