快速排序算法--Ruby实现

Question

我一直在努力调试我的快速排序实现，并且可以使用一双新的眼睛。我正在学习 Robert Sedgewick 的 Coursera 算法课程，我完全不知道我这样做的方式有什么问题（看起来与他的 java 实现几乎相同）。有任何想法吗？我知道我的分区方法是有效的，因为我已经对其进行了广泛的压力测试（即，如果我提交低为 0 和高为 2，则数组将在这些索引之间正确分区）。

另外，我使用快速排序作为就地排序，所以这就是我不创建辅助数组的原因。

def shuffle(arr)
  arr.each_index do |i|
    r = rand(0..i)
    arr[i], arr[r] = arr[r], arr[i]
  end
  arr
end

def partition!(arr,low, high)
  #debugger
  arr = shuffle(arr)
  i = low + 1 
  j = high
  while true 
    until arr[i] >= arr[low]
      break if i >= high
      i+=1
    end

    until arr[j] <= arr[low]
      j-=1
    end

    if i>=j 
      #done 
      arr[j], arr[low] = arr[low], arr[j]
      break 
    else 
      #swap and continue
      arr[i], arr[j] = arr[j], arr[i]
    end
  end 
end


def quicksort(arr, low = 0, high=arr.length-1)
  arr = shuffle(arr)
  quicksort!(arr, low, high)
end

def quicksort!(arr, low, high)
   #p "Quicksorting on low index #{low} and high index #{high}"
   return arr if (high <= low)
   j = partition!(arr, low, high)
   quicksort!(arr, low, j-1)
   quicksort!(arr, j+1, high)
end

Answer 1

你快到了。

问题

#1

partition 应该 return j。见对应的java code.

#2

您已经在 quicksort 中打乱了数组，无需在 partition 中一次又一次地打乱它！

此外，请注意，您的 shuffle 方法会随机播放整个数组，独立于 j、low 和 high。

在每次迭代中仅分别改组左右子数组是可行的，即使它是不需要的。

#3

quicksort 应该 return arr.

完整代码

def shuffle(arr)
  arr.each_index do |i|
    r = rand(0..i)
    arr[i], arr[r] = arr[r], arr[i]
  end
  arr
end

def partition!(arr,low, high)
  i = low + 1 
  j = high
  while true 
    until arr[i] >= arr[low]
      break if i >= high
      i+=1
    end

    until arr[j] <= arr[low]
      j-=1
    end

    if i>=j 
      #done 
      arr[j], arr[low] = arr[low], arr[j]
      break 
    else 
      #swap and continue
      arr[i], arr[j] = arr[j], arr[i]
    end
  end 
  j
end


def quicksort(arr, low = 0, high=arr.length-1)
  arr = shuffle(arr)
  quicksort!(arr, low, high)
  arr
end

def quicksort!(arr, low, high)
   return arr if (high <= low)
   j = partition!(arr, low, high)
   quicksort!(arr, low, j-1)
   quicksort!(arr, j+1, high)
end

arr = [3,2,1,4,5]
p quicksort(arr)
# => [1, 2, 3, 4, 5]

快速排序算法--Ruby实现

Quicksort Algorithm--Ruby Implementation

ruby

algorithm

quicksort

问题

#1

#2

#3

完整代码