CODEWITHSUNDEEP
arraysjuliaquicksort
Joel Cummings
Joel Cummings

Reputation: 83

Julia Quicksort Implementation Very Slow Tips?

I implemented a Quicksort using Hoare's partitioning method. It's a simple port over from C however, while C can easily sort thousands of numbers in a fraction of a second using this method, my Julia implementation chokes at 50 numbers. I have tried it with a small set 15 numbers and it sorts correctly so perhaps there is some optimization I'm missing. The numbers I'm sorting are randomly generated and are not in order so it will avoid the n^2 pitfall.

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()

Upvotes: 0

Views: 726

Answers (1)

jarmokivekas
jarmokivekas

Reputation: 187

Having had a quick look, it seems there is a logic flaw somewhere in the code that makes it hang if the input items array contains any elements with the same value. I suspect this might be caused by the fact that arrays in Julia are indexed starting from 1, not from 0 as in C. Maybe look into that.

If you just want to use a quicksort algorithm, there is one available in the Julia base libraries:

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

Find it in the docs.

You can use sort!(a, alg=Base.Sort.QuickSort) if you need to avoid namespace conflicts, as your own function happens to have the exact same name.

Upvotes: 3

Related Questions