Julia Quicksort 实现非常慢的提示？

Question

我使用 Hoare 的分区方法实现了快速排序。这是 C 的一个简单移植，但是，虽然 C 可以使用这种方法在几分之一秒内轻松地对数千个数字进行排序，但我的 Julia 实现在 50 个数字时会卡住。我已经用一组 15 个数字尝试过它并且它排序正确所以也许我缺少一些优化。我正在排序的数字是随机生成的，没有按顺序排列，因此可以避免 n^2 陷阱。

function QuickSort(items, lo, high)

  if (lo < high)
    p = partition(items, lo, high)
    QuickSort(items, lo, p)
    QuickSort(items, p+1, high)
  end
end

function partition(items, lo, high)

    pivot = items[lo]
    i = lo
    j = high

    while true

        while (items[i] < pivot)
            i += 1
        end

        while (items[j] > pivot)
            j -= 1
        end

        if (i >= j)
          return j
        end

        temp = items[i]
        items[i] = items[j]
        items[j] = temp

    end
end

function main()
  stdin_input = Int64[]

  for line in eachline(STDIN)
      push!(stdin_input, parse(Int64, line))
  end

  println("Entering QuickSort")
  QuickSort(stdin_input, 1, length(stdin_input))
  println("QuickSort Complete")
  print(stdin_input)
end


main()

Answer 1

快速浏览了一下，代码中似乎存在逻辑缺陷，如果输入 items 数组包含任何具有相同值的元素，代码就会挂起。我怀疑这可能是由于 Julia 中的数组是从 1 开始索引的，而不是像 C 中那样从 0 开始索引。也许可以研究一下。

如果您只想使用快速排序算法，Julia 基础库中提供了一种算法：

a = [123,42,12,1,4]
sort!(a, alg=QuickSort)

找到它 in the docs。

如果您需要避免命名空间冲突，您可以使用 sort!(a, alg=Base.Sort.QuickSort)，因为您自己的函数恰好具有完全相同的名称。

Julia Quicksort 实现非常慢的提示？

Julia Quicksort Implementation Very Slow Tips?

arrays

quicksort

julia