Быстрая сортировка в Руби язык

Question

Я пытаюсь реализовать быструю сортировку в рубин, но застрял в том, как называть рекурсивно после первого раздела поворота. Пожалуйста, помогите мне понять, как действовать дальше, а также дайте мне знать, хорош ли мой стиль кодирования.

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 

Answer 1

Вот (очень) наивная реализация быстрой сортировки на основе Wikipedia's simple-quicksort pseudocode:

def quicksort(array) #takes an array of integers as an argument 

Вам нужен базовый вариант, в противном случае ваши рекурсивные вызовы никогда не прекращает

if array.length <= 1 
    return array 

Теперь выбрать pivot:

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 

Теперь, рекурсивный вызов quicksort() на ваших less и greater массивов.

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 

Answer 2

Это, как я бы реализовать быструю сортировку в 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 

Answer 3

вот еще один способ реализовать quicksort - как новичок, я думаю, что это легче понять - надеюсь, что это помогает кому-то :) в этой реализации опорный элемент всегда является последним элементом массива - я следую за Khan Academy course, и это где я получил вдохновение от

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]