Algorithm Quicksort Analysis (Part 1)

Today in my "Diary" I will handle the quicksort algorithm.

First I will start with a basic summary and to apologize that in this part only a small Elixir example will be shown. Which I will try to explain in Part 2 in detail, along with the other versions of implementations.

This is an algorithm that works with partitioning the given sets of inputs to work more efficient. It has been developed because of magnetic bands and is based on end-recursions.

Implemented the first time according to wikipedia in ALGOL which means algorithmic language which supports recursions. you can read more about it on the wikipedia pages.

Time complexity

• Avg. Θ(n log n) which is bad but still better than the three - insert, selection, bubble algorithms - mentioned before
• Best case is Θ(n log n) with one partition but Θ(n) with 3 partitions.
• Worstcase is Θ(n²) which makes it in the worstcase scenario as slow as insertion., bubble- and selection-sort so far.

this an algorithm where implementation is key ! if the implementation picks the most left element as pivotal point an already sorted input will lead to worst case of Θ(n²)

There are two commonly known implementations for the partitioning you got the

• Lomuto partition scheme which will lead to to the above mentioned worst cases if all elements are the same or the set has already been sorted
• Hoare partition scheme which in general is faster (it's the Θ(n) version) but it degrades to Θ(n²) as well if the set already has been sorted before ....

looking at the hoare partitioning scheme we could fix the Θ(n²) time complexity problem by picking the pivot points on random.

something like random(start of partition range, end of partition range) or we could take the median of all 3 partitions as pivotal point. which is solved with this algorithm:

lowest index of the array + (highes index of the array−lowest index of the array)/2

which results in an always valid pivotal median. this reduces the probability of the worst cases and leaves us with an efficient sorting algorithm.

Space complexity

• Θ(n) (Lomuto partition scheme as well hoare without the sedgewick optimizations)
• Θ(log n) hoare with sedgewick optimizations

The sedgewick optimization for space complexity in short states to recurse into the smaller sized partition and than tail recurse through the large one

So if we take those things into account a modern quicksort implementation should run in Θ(n) time using Θ(log n) space. this beats the previous algorithms.

short detour semantics partitioning

I will make a short detour and explain what's meant with partitions, those who are a bit older may refer to them as segments for those using go or modern languages one might compare them to slices, i also heard chunks, packages and so on. if we got an array with [1,2,3,4,5,6] and split it into two partitions (split it in half)

we get 2 partitions

G = {1,2,3,4,5,6}
Partition1 = {x∈G, i∈iG| ix > 0 ∧ ix < |G|/2}
Partition2 = {x∈G, i∈iG| ix >= |iG|/2 ∧ i < |G|}

So partitioning just means to take smaller parts of the whole and look at them separate. There are differences between languages and implementations but the basic semantics of splitting something bigger into into smaller parts (partitions,segments,slices,ranges,chunks, ...) should now be clear. (please correct my math-expressions if they are wrong)

Elixir

so why elixir ? well I regularly participate at the we love programming languages in vienna and one of the workshops was elixir with one of the guys who is one of the devs of Rabbit-MQ in Erlang. So he actually really knew so many interesting details about the Erlang-VM as well as the Elixir language about tail-recursions, the process architecture and other concepts of the language and other nice gimmicks like writing unit-test as comments and so on.

So what is elixir ? elixir is a functional language using the erlang VM erlang is the language used by mobile phone companies it is optimized for concurrency as well as fault-tolerant using it's own inbuilt process monitoring and so on.

found Algorithm via google search

So I started with the repos just to have a look at a solution, as you can see in the code and the comment there is no tail recursion obviously there can't be any since the everything but the return value needs to be stateless.

# Not tail recursive and uses ++ :(
defmodule Quicksort do
  def sort([]), do: []

  def sort([head | rest]) do
    {before, after} = Enum.partition(rest, &(&1 < head))
    sort(before) ++ [head] ++ sort(after)
  end
end

small detour to the callstack and tail recursions

So put to it simple, we all know what a stack is, it's the FILO) concept (first in last out) we just add things onto the stack and we need to remove the last thing we put onto it before getting to the one before. of an operation system. In languages like C you have to manage the memory yourself in others like Java the VM handles the memory.

So the question is what has the stack to do with tail recursions ? I will try to explain it based on the following example.

func main()  { 
    print addUpToLimit(10, 12, 200)
}

func addUpToLimit(int value, int interval, int limit) {
    if value + interval >= limit {
        return value + interval
    }

    return addUpToLimit(value + interval, interval, limit)

}

For this example we assume that we don't use references, so there is no writing cross stack address rooms which means our stacks are encapsulated hence immutable.

The call-stack / activation record is the address-space in memory needed for execution of an routine.

It consists of the following 3 things:

1. the passed variables from the caller
2. the return address
3. the space needed for local variables

if we now look at the stack flow of the application it goes as follows

-> main() -> print addUpToLimit(value, interval, limit) -> addUpToLimit(value, interval, limit) -> addUpToLimit(value, interval, limit) -> .....

if we look at this without tail recursions a simple representation of what the stack looks like follows:

| 0| 0 | main           | 
| 1| 0 | print addUpToLimit(10, 12, 200) | 
| 2| 1 | int value    | 10
| 3| 1 | int interval | 12
| 4| 1 | int limit    | 200
| 6| 1 | @return #0   |
| 7| 1 | addUpToLimit | 
| 8| 2 | int value    | 22
| 9| 2 | int interval | 12
|10| 2 | int limit    | 200
|11| 2 | @return #6   |
|12| 2 | addUpToLimit |
|13| 3 | int value    | 34
|14| 3 | int interval | 12
|15| 3 | int limit    | 200
|16| 3 | @return #12  |
...
|n | n | .........
...
|96| 16 | @return #15 | 202
|97| 15 | @return #14 | 202
|98| 14 | @return #13 | 202
.............

As you can see this is rather expensive memory wise, so you understand why it's Θ(n) in space complexity because every function call pushes another activation record onto the stack.

This is one of the origin of the famous quote of Alan Perlis

LISP programmers know the value of everything and the cost of nothing.

As well as why imperative languages dominated the industry for such a long time. The loop expression is mutable and does not need a call stack. so in memory efficiency it's way better than a recursion. At the time Memory and CPUs were expensive. With the steady improvements of modern VMs and compilers the functional language is getting it's comeback.

What is the concept of a tail recursion ? the idea of it is to turn the function body to a loop. If we look at the addUpToLimit function we already can spot reusable parts the way it is built it's statless

so instead of using the positions 1 to 17+ we only need 1 to 7 and reuse them since we actually don't need to remember the previous state and only are concerned what goes in every time in the next function call.

| 0| 0 | main           | 
| 1| 0 | print addUpToLimit(10, 12, 200) | 
| 2| 1 | int value    | n
| 3| 1 | int interval | x
| 4| 1 | int limit    | y
| 6| 1 | @return #0   |

This is why the space complexity turns from Θ(n) to Θ(log n) but after the quicksort optimizations. because we reuse the last activation record. the stack would be Θ(1) but we still need space for the variable change vectors.

What is important for a tail recursion is:

1. it's not allowed to use another initialization record inside -> so it's not allowed to call another function.
2. it's not allowed to return anything but data -> it only can recurse onto itself or return the calculated value(s)

This is where i stop for this iteration. Part 2 will include all 3 algorithms implementations ins Elixir explained in detail as SPL as well as hopefully 1 multi thread implementation.

Thanks for reading :) please leave a comment and correct my math or any other thing I might explained wrong :)