Quick Sort Time Complexity

Quick Sort, also written as quicksort, is a divide-and-conquer sorting algorithm. When coded, the quicksort program would consist of a swap() function, a pivot() function, a partition() function, and the quicksort function itself. Both the pivot() and partition() functions call the swap() function. The quicksort() function itself is short and calls the pivot() and partition() functions. It recursively calls itself in two places within its body.

Now, there are different ways of writing the pivot() and partition() functions. The choice of the type of pivot() function and/or partition() function determines the efficiency of the whole program. Efficiency is like the number of main operations that are carried out by the program.

Time complexity is the relative runtime of a program. This can be seen as the main operation of the program.

Sorting can be ascending or descending. In this article, sorting is ascending.

The aim of this article is to produce the time complexity for a quicksort program. Since quicksort can be written in different ways depending on the choice of the pivot() and/or the partition() functions, each quick-sort type has its own time complexity. However, there is a range of a number of operations into which the different types of quicksort programs fit. This article presents just one of the different types of quicksort programs. Any code segment presented is of the C language.

Integer Division by Two

Quick Sort uses integer division in dividing its main set into smaller sets.

Now,
11 / 2 = 5 remainder 1

Integer division means, taking 5 and abandoning 1. That is, accept the whole number and ignore the remainder.

Also,
10 / 2 = 5 remainder 0

Here, the remainder is zero and does not matter. Still, integer division takes 5 and abandons 0. That is, accept the whole number and ignore whatever remainder is there, even if it is zero. Sometimes in programming, it is also good to know whether the remainder is 0 or not – see later.

When dividing a list in quick-sort, integer division is what is used.

For quick sort, to obtain the zero-based middle index for a list, do integer division by two for the length of the list. The whole number is the zero-based, middle index. To obtain the length of the list, start counting from 1.

Time Complexity Related to Quick Sort

Consider the following code:

The output is:

That is, all eight elements have been printed.

There are eight elements identified by n. The body of the for-loop has a content.

This is one main operation. So, eight main operations have taken place. The time complexity for this code is written as:

O(n)

Where n is the number of main operations. This is the Big-O notation. In the notation, the first letter is O in uppercase. Then there are parentheses. Inside the parentheses is the number of operations or maximum possible number of operations.

Now consider the following code segment:

The output is:

The body of the for-loop has a content.

This is still considered one main operation in this situation. Three elements have been printed because the main operation has been executed three times.

Now,
8 = 2³
=>   3 = log₂(8)

If 8 is n, then 3 is,
log₂(n)

And the time complexity would be given as:
O(log₂n)

There is still another code segment to consider in relation to quicksort time complexity. It is

The output is:

The number of characters printed is 64, from an initial number of 8. This means that the main operation has been executed 64 times.

64 = 8 x 8 = 8²

If 8 is n, then this would be n². The time complexity for this code is:
O(n²)

Quick Sort Algorithm in this Article

For this article, the steps of the algorithm are:

• Look for the median (see below) between the first element, middle element, and last element of the list.
• Position the median in the middle of the list.
• Send all the elements on the right that are less than the median, now in the middle, to the left of the median, and send all the elements on the left that are greater than the median to the right of the median. This is called partitioning.
• Repeat the above three steps in order, for each sub-list, until the list has been separated into single elements.
• When the list consists of separated single elements, the list is sorted.

Median

To obtain the median of the three elements,

rearrange the three elements in order, i.e.

The middle element, B, is the median.

Quick Sort Illustration

The list to be sorted is:

There are eight elements. When the list has been sorted, it would be:

So, the problem is: sort the list:

using quicksort.

The median between P, Q, and B is looked for. It is P. This search for the median involves three operations. So, there are a total of three operations so far. Putting the median in the middle of the list gives:

Remember: the index for the middle element is the result of the integer division by two. There are four movements here, for P and Q. Those are four operations. That makes a total of seven operations so far (three plus four). Now, B will be sent to the left, and V and Q will be sent to the right, to have:

Note that P is no longer at the true middle. However, there were three movements. These are three operations. So there are ten operations so far (seven plus three). Each of the two sub-lists has to be split into three parts (the median is one part).

The median for D and B is D. The search for the median is three operations. That makes a total of thirteen operations so far (ten plus three). Partitioning these elements gives:

There were two movements here. Those are two operations. This makes a total of fifteen operations so far (thirteen plus two). Next, the median for the set {V, Q, S, X, T} has to be looked for, and the set partitioned.

The median for V, S, and T is T. The median search is three operations. So far, there have been eighteen operations (fifteen plus three). Putting T in the middle gives:

There are three movements here. These are three operations. The total number of operations so far is twenty-one (eighteen plus three). Sending lower elements on the right of T to the left, and higher elements on the left of T to the right, gives:

There are two movements here. These are two operations. So far, there is a total of twenty-three operations (twenty-one plus two). Putting all the partitions together so far gives:

Notice that the list is already sorted. However, the algorithm has to terminate. {Q, S} and {V, X} have to be attended to. There will be no movement of characters between these two. However, their median will be looked at. The search for two medians is six operations. This makes a total of twenty-nine operations for the whole program (twenty-three plus six). The final sorted list is:

Note:
24 = 8 x 3
=>    24 = 8xlog₂8

29 is approximately equal to 24.

Conclusion

Depending on the type of function chosen for pivot() and the type of function chosen for partition(), the time complexity for the quicksort program will be somewhere between

O(n.log₂n)

and

O(n²)

inclusive. Note that the dot in O(n.log₂n) means multiplication.