Python: Quick sort

Last update on April 23 2025 12:56:58 (UTC/GMT +8 hours)

9. Quick Sort

Write a Python program to sort a list of elements using the quick sort algorithm.
Note : According to Wikipedia "Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting."

Sample Solution:

Python Code:

def quickSort(data_list):
   quickSortHlp(data_list,0,len(data_list)-1)

def quickSortHlp(data_list,first,last):
   if first < last:

       splitpoint = partition(data_list,first,last)

       quickSortHlp(data_list,first,splitpoint-1)
       quickSortHlp(data_list,splitpoint+1,last)


def partition(data_list,first,last):
   pivotvalue = data_list[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and data_list[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while data_list[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = data_list[leftmark]
           data_list[leftmark] = data_list[rightmark]
           data_list[rightmark] = temp

   temp = data_list[first]
   data_list[first] = data_list[rightmark]
   data_list[rightmark] = temp


   return rightmark

data_list = [54,26,93,17,77,31,44,55,20]
quickSort(data_list)
print(data_list)

Sample Output:

[17, 20, 26, 31, 44, 54, 55, 77, 93]

Flowchart:

For more Practice: Solve these Related Problems:

Write a Python program to implement quick sort and print the pivot element chosen at each recursive call.
Write a Python script to sort a list using quick sort and measure the recursion depth required for sorting.
Write a Python program to implement quick sort using the Lomuto partition scheme and compare its performance with Hoare's partition scheme.
Write a Python function to sort a list of strings using quick sort and ensure the sort is case-insensitive.

Go to:

Previous: Write a Python program to sort a list of elements using the merge sort algorithm.
Next: Write a Python program Program for counting sort.

Python Code Editor :

Contribute your code and comments through Disqus.