4
\$\begingroup\$

Similar to this question here, I am trying to implement sort algorithms in Julia, as part of a package.

The code for the implementation is as follows:

"""
The swapping function implementation
"""
function swap!{T}(x::AbstractArray{T}, a::T, b::T)

  tmp = x[a]
  x[a] = x[b]
  x[b] = tmp
  return x

end


"""
`insertsort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Insertion Sort** approach.
"""
function insertsort!{T}(x::AbstractArray{T})

  for index = 2:length(x)

    current  = x[index]
    position = index

    # For sublist sorting
    while position > 1 && x[position - 1] > current
      x[position] = x[position - 1]
      position -= 1
    end

    x[position] = current

  end

  return x
end


"""
`bubblesort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Bubble Sort** approach.
"""
function bubblesort!{T}(x::AbstractArray{T})

  for i in 2:length(x)
    for j in 1:length(x)-1
      if x[j] > x[j+1]
        swap!(x, j, j+1)
      end
    end
  end

  return x
end


"""
`selectsort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Selection Sort** approach.
"""
function selectsort!{T}(x::AbstractArray{T})

  for i in 1:length(x)-1
    iMin = i
    for j in i+1:length(x)
      if x[j] < x[iMin]
        iMin = j
      end
    end

    swap!(x, i, iMin)
  end

  return x
end


"""
`quicksort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Quick Sort** approach.
"""
function quicksort!{T}(x::AbstractArray{T}, first::T = 1, last::T = length(x))

  if last > first

    pivot       = x[first]
    left, right = first, last

    while left <= right
      while x[left] < pivot
        left += 1
      end
      while x[right] > pivot
        right -= 1
      end
      if left <= right
        swap!(x, left, right)
        left += 1
        right -= 1
      end
    end

    quicksort!(x, first, right)
    quicksort!(x, left, last)
  end

  return x
end


"""
`mergesort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Merge Sort** approach.
"""
function mergesort!{T}(x::AbstractArray{T})

  if length(x) > 1
    mid    = div(length(x), 2)
    left   = mergesort!(x[1:mid])
    right  = mergesort!(x[mid+1:length(x)])
    result = Array(eltype(left), length(left) + length(right))

    k = 1

    while length(left) != 0 && length(right) != 0
      if left[1] <= right[1]
        result[k] = left[1]
        left      = left[2:end]
      else
        result[k] = right[1]
        right = right[2:end]
      end
      k += 1
    end

    while length(left) != 0
      result[k] = left[1]
      left = left[2:end]
      k += 1
    end

    while length(right) != 0
      result[k] = right[1]
      right = right[2:end]
      k += 1
    end

  for i = 1:length(x)
    x[i] = result[i]
  end

  end

  return x
end

All the sort algorithms are in-place. Are there any ways I can make speed up the implementations along with optimizing code for performance and quality?

(The reason I created a separate swap function, rather than doing x[a], x[b] = x[b], x[a] is that I felt it'd look more neat. Need your views on that too,)

\$\endgroup\$
  • \$\begingroup\$ result = Array(eltype(left), length(left) + length(right)): are you creating an array right there? \$\endgroup\$ – coderodde Mar 8 '16 at 8:56
  • \$\begingroup\$ @coderodde Yes. eltype gives the Type and length(left) + length(right) gives the requisite length \$\endgroup\$ – Dawny33 Mar 8 '16 at 9:00
  • \$\begingroup\$ For this very reason your mergesort is not in-place. \$\endgroup\$ – coderodde Mar 8 '16 at 9:10
  • \$\begingroup\$ @coderodde I should confess that that was a hack to make it look like in-place :) (Would be changing a later). \$\endgroup\$ – Dawny33 Mar 8 '16 at 10:09
  • \$\begingroup\$ Actually there exists an in-place mergesort, yet, as far as I recall, it's slower by the factor of \$\Theta(\log n)\$. \$\endgroup\$ – coderodde Mar 8 '16 at 10:31
1
\$\begingroup\$

Your mergesort has a serious issue. If you run

size=100000
x=rand(1:(2^62),size)
@time(mergesort!(x))

you will find that your algorithm is allocating ram 2.34 million times, and is allocating 37.4 GB The problem comes from this block:

while length(left) != 0 && length(right) != 0
  if left[1] <= right[1]
    result[k] = left[1]
    left      = left[2:end]
  else
    result[k] = right[1]
    right = right[2:end]
  end
  k += 1
end

If you instead write,

left_ind = 1
right_ind = 1
r_ind = 1
while left_ind<=length(left) && right_ind<=length(right)
    if left[left_ind]<right[right_ind]
        result[r_ind]=left[left_ind]
        left_ind += 1
    else
        result[r_ind]=right[right_ind]
        right_ind += 1
    end
    r_ind += 1
end
if left_ind<=length(left)
    result[r_ind:end] = left[left_ind:end]
elseif right_ind<=length(right)
    result[r_ind:end] = right[right_ind:end]
end
result

This drops the time from 3.7 seconds to .2 seconds, and memory allocation to 57MB

\$\endgroup\$
  • 1
    \$\begingroup\$ It turns out that since you were creating n arrays when merging arrays of size n, you managed to make a version of mergesort that had runtime ~ O(n^2log(n)). \$\endgroup\$ – Oscar Smith Jul 28 '16 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.