Quick sort in python

 Quick sort also use divide and conquer strategy.

In this we find out the correct position for the pivot element and partition the list into two this method is called partition method. Then further seperate the list as same. This method is the backbone of the quick sort.

Using pivot element we going to sort the list. We should follow few condition for quick sort

1) pivot element

2) if start is less than pivot increment

3) if end is greater than pivot increment

[---lesser num--, pivot, --- greater num---] 

Number less than pivot should be in left and greater should be in right as above format.

We see more clearly in a example

Algorithm:

Example:

Take list[5, 16, 23, 45, 61, 34, 4]

Take 5 as pivot element

pivot = 5
start = list[o]=5
End = list[6]=4

Now start comparing from start and end

i) if start is less than or equal pivot increment

ii) if end is great than pivot increment

iii) when both condition false then swap

-5 is less than or equal pivot, yes so increment
-16 is less than pivot, no so stop
-now check end 4 greater than pivot, no so stop

Now both the condition are false so swap (16,4) follow same for other elements as shown in below.

                                           

                                                                      10 > pivot so stop

                                                                    Now check end

swap(10,2)

                        start and end intersected or end less than start swap(end,pivot)

                                                               (5,7)

 

Take [5, 6, 2] as list1 and [9 , 10, 15, 8] as list follow same method for list1 and list2.

[5,6,2]

Pivot = 5

6 > 5 and 2 < 5 so swap(6,2)

End and start intersected so swap pivot and end

 

When you follow same step for list2 at last you get......

Now combine all the sublist to get a sorted list

Code  for Quick sort:

def partition(list, low, high):

    i = (low-1)         

    pivot = list[high]     

  

    for j in range(low, high):

  

        

        if list[j] <= pivot:

  

            

            i = i+1

            list[i], list[j] = list[j], list[i]

  

    list[i+1], list[high] = list[high], list[i+1]

    return (i+1)

  

  

  

def quickSort(list, low, high):

    if len(list) == 1:

        return list

    if low < high:

  

        

        pi = partition(list, low, high)

  

        

        quickSort(list, low, pi-1)

        quickSort(list, pi+1, high)

  

  

# Driver code to test above

list = [10, 7, 8, 9, 1, 5]

n = len(list)

print("before sorting:",list)

quickSort(list, 0, n-1)

print("Sorted array is:")

for i in range(n):

    print("%d" % list[i]),

print("after sorting:",list)

  

Output:

before sorting: [10, 7, 8, 9, 1, 5] Sorted array is: 1 5 7 8 9 10 after sorting: [1, 5, 7, 8, 9, 10]

  

Hope you understand the program and try yourself for more clear view ,feel free to comment your thoughts!!