# What is the difference between these two implementations?

**URL:** <https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426>\
**Category:** New to Julia\
**Tags:** question, quicksort\
**Created:** [September 15, 2024, 7:24am UTC](https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426 "2024-09-15T07:24:52Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![kands-code](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kands-code/32/211969_2.png) [@kands-code](https://discourse.julialang.org/u/kands-code)\
**Post date:** [September 15, 2024, 7:24am UTC](https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426/1 "2024-09-15T07:24:52Z")

</div>

I recently came across the programming language Julia, which is a very efficient language with a lot of tools that allow me to complete some tasks easily.  
But I encountered a problem when learning how to use Julia to write a quick sort algorithm (using Hoare partition). In [Wikipedia](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme), Hoare partition is implemented using a do-while loop,which is not directly available in Julia, so I initially planned to use a basic while loop to avoid the do-while loop, and I had the following implementation:

```julia
begin
	function quick_sort_hoare(
		lst::Vector{N};
		lb::Integer = 1,
		ub::Integer = length(lst)
	)::Vector{N} where { N } 
		copied_lst = copy(lst)
		quick_sort_hoare!(copied_lst, lb, ub)
		copied_lst
	end

	function quick_sort_hoare!(lst::Vector{N}, lb::Integer, ub::Integer) where { N }
		if lb < 1 || ub < 1 || lb >= ub
			nothing
		else
			pivot_index = hoare_partition!(lst, lb, ub)
			quick_sort_hoare!(lst, lb, pivot_index)
			quick_sort_hoare!(lst, pivot_index + 1, ub)
		end
	end

	function hoare_partition!(
		lst::Vector{N},
		lb::Integer,
		ub::Integer
	)::Integer where { N }
		pivot = lst[lb]
		left_index = lb
		right_index = ub
		while true
			while lst[left_index] < pivot
				left_index = left_index + 1
			end
			while lst[right_index] > pivot
				right_index = right_index - 1
			end
			if left_index >= right_index
				break
			end
			lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
		end
		right_index
	end
end

```

But the algorithm implemented above is very slow and may not even work properly, so I adjusted the loop implementation, which is the following code:

```julia
begin
	function quick_sort_hoare(
		lst::Vector{N};
		lb::Integer = 1,
		ub::Integer = length(lst)
	)::Vector{N} where { N } 
		copied_lst = copy(lst)
		quick_sort_hoare!(copied_lst, lb, ub)
		copied_lst
	end

	function quick_sort_hoare!(lst::Vector{N}, lb::Integer, ub::Integer) where { N }
		if lb < 1 || ub < 1 || lb >= ub
			nothing
		else
			pivot_index = hoare_partition!(lst, lb, ub)
			quick_sort_hoare!(lst, lb, pivot_index)
			quick_sort_hoare!(lst, pivot_index + 1, ub)
		end
	end

	function hoare_partition!(
		lst::Vector{N},
		lb::Integer,
		ub::Integer
	)::Integer where { N }
		pivot = lst[lb]
		left_index = lb - 1
		right_index = ub + 1
		while true
			while (left_index = left_index + 1; lst[left_index] < pivot) end
			while (right_index = right_index - 1; lst[right_index] > pivot) end
			if left_index >= right_index
				break
			end
			lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
		end
		right_index
	end
end

```

The second implementation is correct, but I think the two implementations should be the same, so why is this?

Though the question may be very basic, I would appreciate guidance. Thank you in advance for your help.

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [September 15, 2024, 8:23am UTC](https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426/2 "2024-09-15T08:23:50Z")

</div>

Hi, and welcome to the Julia community!

The `while` loops in the two implementations are not equivalent, also when you take into account the different initialisations of `left_index` and `right_index`: in the second implementation you always increment `left_index`, while in the first one this only happens conditionally. For example,

```julia-repl
julia> x = 10;

julia> while x <= 5
           x += 1 # equivalent to x = x + 1
       end

julia> x
10

```

compared to

```julia-repl
julia> x = 10;

julia> while (x += 1; x <= 5) end

julia> x
11

```

Using the first implementation you can then get stuck in an infinite loop when `lst[left_index] == pivot == lst[right_index]`, where you will keep swapping these (equal) list entries and never change `left_index` or `right_index`. You could fix the first implementation by explicitly adding a `left_index += 1` and `right_index -= 1` at the end of the loop:

```julia
function hoare_partition!(
    lst::Vector{N},
    lb::Integer,
    ub::Integer
    )::Integer where { N }
    pivot = lst[lb]
    left_index = lb
    right_index = ub
    while true
        while lst[left_index] < pivot
            left_index = left_index + 1
        end
        while lst[right_index] > pivot
            right_index = right_index - 1
        end
        if left_index >= right_index
            break
        end
        lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
			
        left_index += 1 # <--------------
        right_index -= 1 # <--------------
    end
    right_index
end

```

As a side-note, it’s [generally better](https://docs.julialang.org/en/v1/manual/style-guide/#Avoid-writing-overly-specific-types) to not specify variable types in functions if you don’t have to (e.g. you don’t use `N` in the body of your function). Additionally, the usual convention is to use `T` for a type (like `Float64`), and `N` for a natural number (e.g. `3`, for example if you want to encode a length into the type of a struct, as in `SVector` from StaticArrays.jl).

---

<div class="post-metadata">

**Author:** ![kands-code](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kands-code/32/211969_2.png) [@kands-code](https://discourse.julialang.org/u/kands-code)\
**Post date:** [September 15, 2024, 10:23am UTC](https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426/3 "2024-09-15T10:23:41Z")

</div>

Thank you very much for your help. I finally understand where I went wrong!

In addition, you mentioned the type `N`. That was what I wanted to say that the type in Vector should be `Comparable`, but it seems that there is no similar interface or traits in Julia (I am not familiar with the corresponding term in Julia), so I forgot to remove it. Thanks for reminding me!

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [September 15, 2024, 11:05am UTC](https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426/4 "2024-09-15T11:05:38Z")

</div>

> [@kands-code](#):
>
> In addition, you mentioned the type `N`. That was what I wanted to say that the type in Vector should be `Comparable`, but it seems that there is no similar interface or traits in Julia (I am not familiar with the corresponding term in Julia)

This is a recurring theme. There are no built in traits or interfaces in julia, though there are some packages which creates things that mimics traits and interfaces. Julia typically uses “duck-typing”. If it behaves like a duck, it is a duck. In particular, elements of a type are comparable if the function `Base.isless` works for them, or `<` (if it’s a partial order). I.e. if you create your own type and want it to work with sorting and other algorithms doing comparisons, just define:

```julia
Base.isless(a::MyType, b::MyType) = mycomparisonfunction(a, b)
# or
Base.:(<)(a::MyType, b::MyType) = mycomparisonfunction(a, b)

```

[https://docs.julialang.org/en/v1/base/sort/#Alternate-Orderings](https://docs.julialang.org/en/v1/base/sort/#Alternate-Orderings)

---

<div class="post-metadata">

**Author:** ![kands-code](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kands-code/32/211969_2.png) [@kands-code](https://discourse.julialang.org/u/kands-code)\
**Post date:** [September 15, 2024, 1:25pm UTC](https://discourse.julialang.org/t/what-is-the-difference-between-these-two-implementations/119426/5 "2024-09-15T13:25:25Z")

</div>

Thank you for the documentation reference!