QuickSort Python Iterative and Recursive implementations

QuickSort is one of the most famous sorting algorithms in computer science. I implemented the QuickSort in Python using two approaches including Recursive QuickSort and Iterative QuickSort.

The implementation were done in Python to explore a different approach than the traditional C and Java languages. Finally I scored the average running time obtained by running multiple times each approach.

System Configuration

The following are the system configurations used for benchmarking:

Python version: 2.7.5
Operating System: OS X 10.9.4
RAM Memory: 8GB
Processor 2.4 GHz Intel Core i5

Recursive QuickSort Python

The recursive quick sort version of this algorithm was implemented using the traditional divide and conquer paradigm: First choose a pivot (first element of the list in this case) and move all elements lower than the pivot to the left or elements greater than the pivot are move to the right. Then continue sorting the left side and the right side This algorithm is expected to have an average performance of the order of (N log N) the worst case of the order of (N2). The performance of this algorithm can be affected by selection of the pivot for the partition. As the input used for this benchmark in a randomly unsorted list the selection of the pivot is not an issue.

Figure 1 shows the log-log plot of the running time as a function of the input size. In this plot it can be seen that the implementation of the algorithms is running as expected. The plot shows a linearithmic order of grow of the function.

Some issues to note about this approach that the recursive calls can take a lot of stack overhead. In the case of Python, the random numbers in the input list varies from 1 to 10000. However, if the program only tries to sort lists where the random numbers are from 1 to 10 the program has a RuntimeError as the maximum recursion depth is exceed. When this is the case the Iterative method is recommended.

Iterative QuickSort Python

For the iterative version of the QuickSort algorithm a Stack was utilised to store elements when partitioning.

The running time of the implementation satisfy the expected result. When referring to Figure 2 it can be seen than the running time as a function of the input size is a linearithmic (N log N).

As this method is iterative there was no issues related to the input number as it was the case of the recursive versions.

Comparison

When comparing both implementation of the algorithms there is not much difference in the running time. However, when these implementations were compared to the Python built in sort function running time there is some constant difference. For instance, for an input of 1 million elements Python’s sort function was 5 time faster. Python running time was just under a second and my implementation was around 5.5 seconds. Refer to figure 3

QuickSort Recursive

 

 

 

QuickSort Iterative

 

 

 

 

 

 

 

The following is the python code I wrote for this implementations.

Running times as a function of the input size (tines in milliseconds):

Screen Shot 2014-11-27 at 12.19.09 am

3 thoughts on “QuickSort Python Iterative and Recursive implementations

  1. daniel

    Excellent ! well written.

    I am studying this kind of benchmarking and Sorting Algorithms in general,
    but am still confused with logarithms sometimes.
    With my tests, I have plotted logN (base10) for the number of elements along the X-axis,
    and the base10 log of time in nanoseconds on the y axis which always seems to give me
    an almost straight line function.
    My teacher has told me not to plot log against linear, but i dont think I have.

    can you please tell me, which kinds of graphs, logged or lin are better for viewing results and why ?
    cheers !
    daniel

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *