快速排序不适用于较大的数组大小

下面是我在ruby中的快速排序代码，它的数组大小像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

来源

2014-11-09 Rahul Dess

您可以发布完整的代码吗？我看不到您发布的代码中定义了“@ tail”。 – Surya 2014-11-09 08:36:07

嘿@ User089247，我保留了整个代码。你是否也可以让我知道我的编码习惯如何。 – 2014-11-09 08:40:20

至少最后的请求似乎更适合[代码评论]（http://codereview.stackexchange.com/）。 – greybeard 2014-11-09 09:07:52

快速排序算法的实现不正确。在线路：
startSort(array, pivot + 1, @tail)
你总是呼吁pivot + 1startSort方法和array.size - 1因为@tail是一个实例变量。它只被分配到@array.size - 1一次，其值永不改变。但是，只需将此行更改为
startSort(array, pivot + 1, tail)
不足以修复您的代码。有了这个改变，即使对于大型数组，它也能快速工作，但会产生不正确的答案这条线实际上应该是：
startSort(array, pivot, tail)。
通过此更改，它可以快速处理大型数组并正确排列数组。

来源

2014-11-09 10:16:39 kraskevich

感谢兄弟！有效。 – 2014-11-09 18:54:05

快速排序不适用于较大的数组大小

回答

相关问题