Quicksort не работает с меньшим размером массива

Question

Ниже приведен мой код быстрой сортировки в рубине, и его работа отлично подходит для размера массива, такого как 20-25, но слишком глубокая ошибка уровня стека или его застревание в течение более длительного времени.

Я предполагаю, что я делаю тривиальную ошибку, но не в состоянии понять.

# This program is to do sorting using Quick sort. 
require 'colorize' 

class QuickSort 
attr_accessor :array 
    def initialize(size) 
    puts "Generating Random numbers for your array".cyan 
    @array = (1..size.to_i).map do 
    rand(500) # Generating random numbers between 1 to 500. 
    end 
    # Boundary case 
    if @array.size == 1 
    puts "Your sorted array is" 
    p @array 
    return 
    end 
    puts "Array Before Sorting".yellow 
    p @array 
    @head = 0 
    @tail = @array.size-1 
    startSort(@array,@head,@tail) #Start the searching logic. 
    end 

# Quicksort logic 
def startSort(array,head,tail) 
    if head < tail 
    pivot = partitionArray(array,head,tail) # Calling the sorting logic 
    startSort(array,head,pivot-1) 
    startSort(array,pivot+1,@tail) 
    end 
end 


# This method is called to partition the array based on pivot. 
def partitionArray(array,head,tail) 
    pivot_value = array[(head+tail)/2] # Choosing random pivot value. 
# Run this partition step until head is equal to tail 
    while head <= tail 
    if array[head] < pivot_value 
    head += 1 
    elsif array[head] >= pivot_value 
    if array[tail] > pivot_value 
     tail -= 1 
    elsif array[tail] <= pivot_value 
     # Swapping head and tail values 
     temp = array[head] 
     array[head] = array[tail] 
     array[tail] = temp 
     # Moving each pointer forward from both the directions. 
     head += 1 
     tail -= 1 
    end  
    end  
    end 
    return head # Nothing but pivot 
end 
end 


puts "Enter the size of Array" 
@size = gets.chomp 
# Checking if entry is a valid integer or not. 
if @size.match(/^(\d)+$/) 
    @obj = QuickSort.new(@size) 
    puts "Array after sorting is ".green 
    p @obj.array 
else 
    puts "Invalid Entry".red 
end 

Answer 1

Ошибка в реализации алгоритма быстрой сортировки. В строке:
startSort(array, pivot + 1, @tail)
вы всегда вызывать startSort метод pivot + 1 и array.size - 1 потому что @tail является переменной экземпляра. Он присваивается @array.size - 1 только один раз, и его значение никогда не изменяется. Однако просто изменить эту строку на
startSort(array, pivot + 1, tail)
недостаточно, чтобы исправить ваш код. С этим изменением он работает быстро даже для больших массивов, но дает неправильный ответ. Эта линия должна быть фактически:
startSort(array, pivot, tail).
С этим изменением он быстро работает для больших массивов и сортирует массив должным образом.