Python Program for Quick Sort

What is quick sort ?

• Quick sort is one of the divide-and-conquer algorithm.
• Quick sort is to sort an array array[0], array[1],....array[n] by picking some element in the array as pivot element around which to rearrange the elements in the array in order to get sorted elements.
• Quick sort reduces the space complexity and removes the use of the auxiliary array that is used in merge sort.
• Use random pivot instead of first array element as pivot element to reduces the time complexity.

Quick Sort Algorithm

• Pick the pivot element in random which can be first element also in the array.
• Move all the elements in left side of pivot element which are less than pivot element.
• Move all the elements in right side of pivot element which are greater than pivot element.
• Partition array elements which are less than pivot element and repeat the process 1 to 3 till all sub array elements in sorted order.
• Partition array elements which are greater than or equal to pivot element and repeat the process 1 to 3 till all sub array elements in sorted order.

Quick Sorting Steps

Quick Sorting Time complexity

Quick Sort Python Program

#!/usr/bin/python                
                                                     
def swap(list_vals, index1, index2):           
    temp = list_vals[index1];                          
    list_vals[index1] = list_vals[index2];                                      
    list_vals[index2] = temp;                                                   
                                                                                
def partition_by_pivot(list_vals, start_index, end_index):                      
    i = start_index + 1;                                                        
    # First element as pivot element.                                           
    pivot_element = list_vals[start_index];                                     
                                                                                
    for j in range(start_index + 1, end_index+1):                               
        # Arranges the list elements which are less than pivot                  
        # on one side and which are greater that on other side.                 
        if (list_vals[j] < pivot_element):                                      
            swap(list_vals, i, j);                                              
            i += 1;                                                             
                                                                                
    # swaps pivot element in correct position                                   
    swap(list_vals, start_index, i-1);                                          
    # returns the updated pivot element position                                
    return i-1;                                                                 
                                                                                
def quick_sort(list_vals, start_index, end_index):                              
    if (start_index < end_index):                                               
         # position of pivot element                                            
         pivot_element_position = partition_by_pivot(list_vals, start_index, end_index);
         quick_sort(list_vals, start_index, pivot_element_position -1);         
         quick_sort (list_vals, pivot_element_position+1 , end_index);          
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [30, 10, 20, 70, 60, 80, 50, 40];                               
    print("Collection before sorting: %s" % str(list_vals));                    
    quick_sort(list_vals, 0, len(list_vals)-1);                                 
    print("Sorted list elements: %s" % str(list_vals));                                                                                                                                                                                                                  

$ python quick_sort.py 
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]