I was reading an interesting article on questions which could come up in interviews for Python developer interviews.
One question was to write code to implement the Quick Sort algorithm.
There are plenty of examples on the net which explain how this particular algorithm works and it is really quite ingenuous.
It was developed by British computer scientist Tony Hoare in 1959 and published in 1961. Even tough it is 60 years old, it is still one of the most efficient ways to sort a list of data.
I love Python because 99 times out of a 100 you can write less lines of code to implement algorithms which are clear, concise and easy to read and follow.
I looked at many Python code examples both on Youtube and on coding blogs and began to despair at how a simple algorithm could be obfuscated by too much code. It looked like C code transposed into Python.
That is until I stumbled across an article in Techie delight. At last, someone who understood Python.
One of Python’s most powerful features is List Comprehension.
A simple implementation would be along the lines of:
Y = [-2*x + 5 for x in range(1,20)]
This will give a list of all the Y co-ordinates for the straight line equation Y = -2X+5
Consider the following code to implement the Quick Sort problem
lst = [4, 2, 9, 8, 12, 34, 23, 6, 5]
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[len(lst) // 2]
left_partition = [x for x in lst if x < pivot]
mid = [x for x in lst if x == pivot]
right_partition = [x for x in lst if x > pivot]
return quick_sort(left_partition) + mid + quick_sort(right_partition)
print(quick_sort(lst))
The pivot point is defined by taking the middle index of the list. List comprehension is used to split the list into left and right partitions. The two lists and pivot are all joined the function is recursively called with the new list until the list is sorted.
I can’t say if this is the fastest or most efficient way in terms of the Big O of implementing the algorithm but I can say that is the clearest way of understanding it and the least verbose way of writing it. If you want to remember how to write code for the Quick Sort in a coding interview, this would be a great example.
