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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#!/usr/bin/env python """ QuickSort Implementations Recursive & Iterative """ def quick_sort_iterative(list_, left, right): """ Iterative version of quick sort """ temp_stack = [] temp_stack.append((left,right)) #Main loop to pop and push items until stack is empty while temp_stack: pos = temp_stack.pop() right, left = pos[1], pos[0] piv = partition(list_,left,right) #If items in the left of the pivot push them to the stack if piv-1 > left: temp_stack.append((left,piv-1)) #If items in the right of the pivot push them to the stack if piv+1 < right: temp_stack.append((piv+1,right)) def quick_sort_recursive(list_, left, right): """ Quick sort method (Recursive) """ if right <= left: return else: #Get pivot piv = partition(list_, left, right) #Sort left side of pivot quick_sort(list_, left, piv-1) #Sort right side of pivot quick_sort(list_, piv+1, right) def partition(list_, left, right): """ Partition method """ #Pivot first element in the array piv = list_[left] i = left + 1 j = right while 1: while i <= j and list_[i] <= piv: i +=1 while j >= i and list_[j] >= piv: j -=1 if j <= i: break #Exchange items list_[i], list_[j] = list_[j], list_[i] #Exchange pivot to the right position list_[left], list_[j] = list_[j], list_[left] return j |

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

danielExcellent ! 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

Jorge ValdiviaPost authorHi Daniel,

It sounds right what you have done. In the Y axis you put the running time and in the X axis the number of items.

To have a better understating of the different order of growth functions and running times have a look at this link http://algs4.cs.princeton.edu/lectures/14AnalysisOfAlgorithms.pdf

JérômeThank you for this nice job.

I was just wondering why is the built-in function so better than yours ?

Best.