Quick sort

In this post, I will be explaining about the people’s favorite sorting algorithm – Quick sort

Quick sort can be done in two ways.

  • Divide and conquer: Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved.
  • In-place: In place sorting algorithms don’t require additional temporary space to store elements as they sort; they use the space originally occupied by the elements.

The steps are:

  • Pick an element, called a pivot, from the list.
  • Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  • Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.
    The base case of the recursion are lists of size zero or one, which never need to be sorted.

Example: In-place algorithm

Code

# /usr/bin/python
# A program to do quick sort using separate list

def quick_sort(inp):
    ''' Quick sort function '''
    lesser = []
    greater = []

    if len(inp) <= 1:
        return inp

    for i in inp[1:]:  
        # 0th element in the list is always the pivot element
        if i < inp[0]:  
            lesser.append(i) 
        else:              
            greater.append(i) 
    return quick_sort(lesser) + inp[0:1] + quick_sort(greater) 

if __name__ =="__main__":
    '''Main function'''

    inp =[]
    s = int(raw_input('How many elements would you like to enter: '))
    for x in range(s):
        inp.append(int(raw_input('Enter element #' + `x+1` + ': ')))
    quick_sort(inp)

Input list:

9 8 3 7 5
[9, 8, 3, 7, 5]
[8, 3, 7, 5] [9]
[3, 7, 5] [8] [9]
[3] [7, 5] [8] [9]
[3] [5] [7] [8] [9]

Output list:

3  5  7  8  9

Example: Divide and conquer

Code

# /usr/bin/python
# A program to do quick sort using inplace algo

def partition(inp, start, end):
    ''' A function which does partition '''
    
    pivot = inp[end]
    bottom = start - 1
    top = end
    
    done = 0
    while not done: 
        while not done:
            bottom = bottom + 1
            if bottom == top:
                done = 1
                break
            if inp[bottom] > pivot:
                inp[top] = inp[bottom]
                break

        while not done:
            top = top - 1
            if top == bottom:
                done = 1
                break
            if inp[top] < pivot:
                inp[bottom] = inp[top]
                break
    inp[top] = pivot
    return top

def quick_sort(inp, start, end):
    ''' Quick sort function '''
    if start < end:
        split = partition (inp, start, end)
        quick_sort(inp, start, split - 1)
        quick_sort(inp, split + 1, end)
    else:
        return

if __name__ == "__main__":
    ''' Main function '''

    inp = []
    s = int(raw_input('How many elements would you like to enter: '))
    for x in range(s):
            inp.append(int(raw_input('Enter element #' + `x+1` + ': ')))
    start = 0
    end = len(inp) - 1
    quick_sort(inp, start, end)        
    import string
    print string.join(map(str, inp))

Input list:

 9 8 3 7 5
[9, 8, 3, 7, 5]  Pivot = 9
[5, 8, 3, 7, [9] Pivot = 5
[3, 8, 5, 7] [9] Pivot = 5
[3] [5] [8, 7] [9] Pivot = 3
[3] [5] [8, 7] [9] Pivot = 8
[3] [5] [7] [8] [9] Pivot = 7 

Sorted list:

3 5 7 8 9

The partition routine examines every item in the array at most once, so it is clearly O(n)
Usually, the partition routine will divide the problem into two roughly equal sized partitions. We know that we can divide n items in half logn times. This makes quicksort a O(nlogn) algorithm.
In worst case, i.e when the list is already sorted, it becomes O(n^2)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s