Quick Sort using Python

Quick sort is a divide and conquer algorithm. In this sort pivot element is chosen for sorting. Usually first element of the list is chosen as pivot element. In this sorting comparison is done to move in forward direction and also in backward direction.

To move in forward direction (from left to right) element values should be less than or equal to pivot element value.

When this condition fails now start moving in backward direction(from right to left), to move so elements values should  be greater than pivot element.

When the above two conditions fail compare value of i and j, if i is less than j, swap a[i] and a[j].

When the above three conditions fails swap a[j] and a[p]. At this point list is broken in to two parts. The left part of pivot  contain elements less than pivot value and the right part contain elements greater than pivot value. Repeat the above process until sorted list is obtained.

Source Code:

def qsort(a,left,right):
    if left<right:
        i=left
        j=right
        p=left
        while i<j:
            while a[i]<=a[p] and i<right:
                i=i+1
            while a[j]>a[p] and j>left:
                j=j-1
            if i<j:
                a[i],a[j]=a[j],a[i]
        a[p],a[j]=a[j],a[p]
        qsort(a,left,j-1)
        qsort(a,j+1,right)
a=[]
n=int(input("enter number of elements"))
for i in range(n):
    a.append(int(input()))
print("List before sorting")
print(a)
left=0
right=n-1
qsort(a,left,right)
print("List after sorting")

print(a)

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of elements5

3

4

2

5

1

List before sorting

[3, 4, 2, 5, 1]

List after sorting

[1, 2, 3, 4, 5]

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html