Get this book > Problems on Array: For Interviews and Competitive Programming
In this article at OpenGenus, we will explore the implementation of Quick Sort in Python using the principles of ObjectOriented Programming (OOP). By utilizing classes and objects, we'll implement the Quick Sort algorithm to efficiently sort arrays or lists of elements.
Table of contents:
 Introduction
 Solution
 Quiz
Introduction
Quick Sort is a widely used sorting algorithm that follows the divideandconquer approach to sort an array or list of elements. The Quick Sort algorithm works by selecting a pivot element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted using the same algorithm. This process continues until the entire array is sorted.
Algorithm
 Choose a pivot element from the array (usually the last element, but other approaches are also possible).
 Partition the array into two subarrays: elements smaller than the pivot and elements greater than the pivot.
 Recursively apply the above steps to the subarrays until the base case is reached (subarrays with zero or one element are considered sorted).
 Combine the sorted subarrays to obtain the final sorted array.
The key steps in the partitioning process involve rearranging the elements such that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. This ensures that the pivot element is in its final sorted position.
Solution
In Python, there are several ways to implement the Quick Sort algorithm. Here are two common types of implementation:
Recursive Implementation
The recursive implementation of Quick Sort follows the divideandconquer approach. It uses a recursive function to divide the array into smaller subarrays, sort them independently, and then combine them to obtain the final sorted array.
 Select a pivot element from the array.
 Partition the array into two subarrays: elements smaller than the pivot and elements greater than the pivot.
 Recursively apply the above steps to the subarrays until the base case is reached (subarrays with zero or one element are considered sorted).
 Combine the sorted subarrays to obtain the final sorted array.
def quick_sort_recursive(self, low, high):
if low < high:
pivot = self.partition(low, high)
self.quick_sort_recursive(low, pivot  1)
self.quick_sort_recursive(pivot + 1, high)
The quick_sort_recursive method is a recursive implementation of Quick Sort. It takes the low and high indices as arguments and recursively partitions and sorts the subarrays until the base case is reached.
Iterative Implementation
The iterative implementation of Quick Sort uses a stack or an auxiliary data structure to simulate the recursive function calls in an iterative manner. It avoids recursion by using loops and stack operations to handle the partitioning and sorting of subarrays.
 Create an empty stack and push the initial boundaries of the array onto the stack (e.g., the lower and upper indices).
 While the stack is not empty, pop the boundaries from the stack.
 Partition the array based on the popped boundaries, obtaining the pivot element's final position.
 Push the boundaries of the subarrays resulting from the partition onto the stack.
 Repeat the above steps until the stack is empty.
def quick_sort_iterative(self, low, high):
stack = [(low, high)]
while stack:
low, high = stack.pop()
if low < high:
pivot = self.partition(low, high)
stack.append((low, pivot  1))
stack.append((pivot + 1, high))
The quick_sort_iterative method is an iterative implementation of Quick Sort. It uses a stack to simulate the recursive function calls. It repeatedly pops boundaries from the stack, partitions the array, and pushes new boundaries onto the stack until the stack is empty.
Class Definition
class QuickSort:
def __init__(self, array):
self.array = array
The QuickSort class is defined. It has a constructor (init method) that takes an input array and initializes the class with it. The input array is stored as an instance variable called array.
Partition Function
def partition(self, low, high):
i = low  1
pivot = self.array[high]
for j in range(low, high):
if self.array[j] <= pivot:
i += 1
self.array[i], self.array[j] = self.array[j], self.array[i]
self.array[i + 1], self.array[high] = self.array[high], self.array[i + 1]
return i + 1
The partition method is a helper function used to divide the array into two halves based on a pivot element. It takes two parameters, low and high, representing the lower and higher bounds of the current partition.
The method selects the pivot as the last element of the current partition (pivot = self.array[high]). It then iterates over the subarray from low to high1. If an element is smaller than or equal to the pivot, it swaps the element with the element at index i+1. This ensures that elements smaller than the pivot are placed before the pivot in the array. Finally, it swaps the pivot element with the element at index i+1 to position the pivot at its correct sorted position. The method returns the index of the pivot.
Recursive Sort Call
def sort_recursive(self):
self.quick_sort_recursive(0, len(self.array)  1)
return self.array
The sort_recursive method is a convenience method that calls the quick_sort_recursive method to perform a recursive QuickSort on the entire array. It starts with the initial lower bound of 0 and the higher bound as the last index of the array. It then returns the sorted array.
Iterative Sort Call
def sort_iterative(self):
self.quick_sort_iterative(0, len(self.array)  1)
return self.array
The sort_iterative method is another convenience method that calls the quick_sort_iterative method to perform an iterative QuickSort on the entire array. It starts with the initial lower bound of 0 and the higher bound as the last index of the array. It then returns the sorted array.
Quick Sort Implementation
array = [6, 2, 9, 1, 5, 10, 8]
qs_recursive = QuickSort(array)
sorted_array_recursive = qs_recursive.sort_recursive()
print("Sorted Array (Recursive):", sorted_array_recursive)
qs_iterative = QuickSort(array)
sorted_array_iterative = qs_iterative.sort_iterative()
print("Sorted Array (Iterative):", sorted_array_iterative)
An example array [6, 2, 9, 1, 5, 10, 8] is created. Then, two instances of the QuickSort class are created: qs_recursive and qs_iterative. These instances are initialized with the example array.
The sort_recursive method is called on the qs_recursive instance to obtain the sorted array recursively. It is stored in the sorted_array_recursive variable. The sort_iterative method is called on the qs_iterative instance to obtain the sorted array iteratively. It is stored in the sorted_array_iterative variable. Finally, the sorted arrays are printed to the console using print statements.
Complete Implementation
class QuickSort:
def __init__(self, array):
self.array = array
def partition(self, low, high):
i = low  1
pivot = self.array[high]
for j in range(low, high):
if self.array[j] <= pivot:
i += 1
self.array[i], self.array[j] = self.array[j], self.array[i]
self.array[i + 1], self.array[high] = self.array[high], self.array[i + 1]
return i + 1
def quick_sort_recursive(self, low, high):
if low < high:
pivot = self.partition(low, high)
self.quick_sort_recursive(low, pivot  1)
self.quick_sort_recursive(pivot + 1, high)
def quick_sort_iterative(self, low, high):
stack = [(low, high)]
while stack:
low, high = stack.pop()
if low < high:
pivot = self.partition(low, high)
stack.append((low, pivot  1))
stack.append((pivot + 1, high))
def sort_recursive(self):
self.quick_sort_recursive(0, len(self.array)  1)
return self.array
def sort_iterative(self):
self.quick_sort_iterative(0, len(self.array)  1)
return self.array
array = [6, 2, 9, 1, 5, 10, 8]
qs_recursive = QuickSort(array)
sorted_array_recursive = qs_recursive.sort_recursive()
print("Sorted Array (Recursive):", sorted_array_recursive)
qs_iterative = QuickSort(array)
sorted_array_iterative = qs_iterative.sort_iterative()
print("Sorted Array (Iterative):", sorted_array_iterative)
Output
Sorted Array (Recursive): [1, 2, 5, 6, 8, 9, 10]
Sorted Array (Iterative): [1, 2, 5, 6, 8, 9, 10]
Time and Space Complexity
Time Complexity :
* Best Case: O(n log n), where n is the number of elements in the array
* Avearge Case: O(n log n), where n is the number of elements in the array
* Worst Case: O(n^2), where n is the number of elements in the array
Space Complexity : O(n), where n is the number of elements in the array
Output Explanation
 Consider the input array: [6, 2, 9, 1, 5, 10, 8].
 Select a pivot element from the array, let's choose the last element (8 in this case).
 Rearrange the elements such that all elements smaller than the pivot are to its left, and all elements greater than the pivot are to its right.
 Left Subarray [2, 1, 5]: The pivot element is 5 (the last element). Rearrange the elements to create subarrays with elements less than 5 and elements greater than 5.
 Right Subarray [9, 10]: The pivot element is 10 (the last element). Rearrange the elements to create subarrays with elements less than 10 and elements greater than 10.
 Combine the sorted subarrays to obtain the final sorted array: [1, 2, 5, 6, 8, 9, 10].
Use of OOP Concepts

Class
: The QuickSort class represents the Quick Sort algorithm. 
Attributes
: The class has an attribute self.array, which stores the array to be sorted. This encapsulates the data related to the sorting process within the class. 
Methods
: The class has methods such as partition, quick_sort_recursive, and quick_sort_iterative, which represent the steps of the Quick Sort algorithm. 
Encapsulation
: By organizing the Quick Sort algorithm within a class, the details of the sorting logic are encapsulated within the class. 
Abstraction
: The class abstracts away the implementation details of the Quick Sort algorithm, making it easier for users to understand and use the sorting functionality.