我试图在ruby中实现快速排序，但在枢轴的第一个分区之后又递归地调用。请帮助我了解如何进行，并让我知道我的编码风格到目前为止是否很好。
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
这是一个基于Wikipedia的Simple-Quicksort pseudocode：
的（非常）幼稚的QuickSort实现。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 = []
循环通过数组，将项目与枢轴进行比较，然后将它们收集到less和greater数组中。
array.each do |x|
if x <= pivot
less << x
else
greater << x
end
end
现在，在您的less和greater阵列上递归致电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, 2, 3, 4, 5] # true
puts qs.quicksort([5]) == [5] # true
puts qs.quicksort([5, -5, 11, 0, 3]) == [-5, 0, 3, 5, 11] # true
puts qs.quicksort([5, -5, 11, 0, 3]) == [5, -5, 11, 0, 3] # false
这是实现QuickSort的另一种方法 - 作为新手，我认为它更容易理解 - 希望它可以帮助某人：）在此实现中，枢轴始终是数组中的最后一个元素 - 我正在关注汗学院课程，这就是我从
中获得灵感的地方def quick_sort(array, beg_index, end_index)
if beg_index < end_index
pivot_index = partition(array, beg_index, end_index)
quick_sort(array, beg_index, pivot_index -1)
quick_sort(array, pivot_index + 1, end_index)
end
array
end
#returns an index of where the pivot ends up
def partition(array, beg_index, end_index)
#current_index starts the subarray with larger numbers than the pivot
current_index = beg_index
i = beg_index
while i < end_index do
if array[i] <= array[end_index]
swap(array, i, current_index)
current_index += 1
end
i += 1
end
#after this swap all of the elements before the pivot will be smaller and
#after the pivot larger
swap(array, end_index, current_index)
current_index
end
def swap(array, first_element, second_element)
temp = array[first_element]
array[first_element] = array[second_element]
array[second_element] = temp
end
puts quick_sort([2,3,1,5],0,3).inspect #will return [1, 2, 3, 5]
我的基于Grokking-Algorithm的递归算法的实现书：
def quick_sort(arr)
return arr if arr.size < 2
pivot = arr[0]
less = arr[1..].select {|el| el <= pivot}
greater = arr[1..].select {|el| el > pivot}
return *quick_sort(less), pivot, *quick_sort(greater)
end
def sort(ary)
return ary if ary.size < 2
pivot = ary[-1]
sm_ary = []
lg_ary = []
ary[0..-2].each do |x|
lg_ary.push(x) && next if x >= pivot
sm_ary.push(x) && next if x < pivot
end
[*sort(sm_ary), pivot, *sort(lg_ary)]
end
arr = [10, 7, 8, 9, 7, 1, 5]
print sort(arr)
# [1, 5, 7, 7, 8, 9, 10]
def quicksort(array)
# if array is empty or has only one element there is no need to sort
return array if array.size <= 1
# for the sake of performance (ms performance :] ) we can always use the first element as a pivot
pivot = array.delete_at(0)
# partition will split array into 2 sub arrays based on the condition passed
# in this case everything smaller than the pivot will be the first array on the left => [[ e < pivot ], [e > pivot]]
# the e qual to pivot will go on the bigger element
left, right = array.partition { |e| e < pivot }
# flatten the multiple sub arrays returned from recursive quicksorts
return [quicksort(left), pivot, quicksort(right)].flatten
end