Ruby 语言中的快速排序 [英] Quick Sort in Ruby language

问题描述

我正在尝试在 ruby​​ 中实现快速排序，但在如何在第一个枢轴分区之后递归调用时遇到了困难.请帮助我了解如何进行，并让我知道到目前为止我的编码风格是否良好.

I am trying to implement Quick sort in ruby but stuck in how to call recursively after the first partition of pivot. Please help me to understand on how to proceed and also let me know whether my style of coding is good so far .

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 中实现快速排序的方式:

This is how I would implement quick sort in Ruby:

def quicksort(*ary)
  return [] if ary.empty?

  pivot = ary.delete_at(rand(ary.size))
  left, right = ary.partition(&pivot.:>)

  return *quicksort(*left), pivot, *quicksort(*right)
end

实际上，我可能会将其设为 Array 的实例方法:

Actually, I would probably make it an instance method of Array instead:

class Array
  def quicksort
    return [] if empty?

    pivot = delete_at(rand(size))
    left, right = partition(&pivot.:>)

    return *left.quicksort, pivot, *right.quicksort
  end
end

这篇关于Ruby 语言中的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！