Quick Sort algorithm in data structures and algorithms using Python

Quick Sort algorithm in data structures and algorithms using Python

Quick Sort Algorithm is used to sort a given list or array into ascending or descending order depending on user preference. This sorting algorithm is very efficient and easy to implement.

Just like merge sort this sorting algorithm is based on the principle of divide and conquer.

FOR EXAMPLE:

INPUT Array: 38 27 43 3 9 82 10

OUTPUT Array: 3 9 10 27 38 43 82

In the following article, we will learn what is Quick Sort Algorithm and how to implement it using Python. We will first see how the sorting algorithm works and furthermore, we will study its algorithm, pseudocode, and lastly its actual implementation in Python.

Table of Contents:

  1. How does the quicksort algorithm work?
  2. Algorithm of QuickSort
  3. Python code for the quicksort algorithm
  4. The time complexity of the quick sort algorithm.
  5. The space complexity of quick sort algorithm.
  6. Is quick sort an in-place sorting algorithm?
  7. Does quicksort show a stable sorting algorithm behavior?
  8. Is quick sort an adaptive sorting algorithm?
  9. Properties
  10. Applications of the quick sort

Working of Quick Sort

Quick Sort is based on the principle of divide and conquer. This algorithm divides the given list or Array into two parts and then solve each part. The partition of the list is done using a pivot element. A pivot element is an element of the list itself.

There are many ways to decide on a pivot element:

  1. The very first element of the Array is chosen as the pivot.
  2. Choosing the last element as pivot.
  3. Picking middle element as pivot.
  4. Randomly choosing any element as a pivot.


The Array is divided such that all the elements to the right of the pivot element are greater than or equal to the pivot and the elements to the left are smaller than the pivot. We implement this sorting algorithm using a recursive call. Using recursion is far more simple and convenient than doing it by iteration.

To understand further let’s take an example

Input: 7, 8, 5, 4, 6, 9

Step 1: Take 7 as the pivot element and divide the array into 2 subarrays.

Step 2: Partition the subarrays further by taking 9 as pivot for the left subarray and 4 as pivot for the right subarray.

Step 3: Once again the partition will take place using 6 as the pivot element.

Step 4: After the sorting is done the final output will be:

Output: 4, 5, 6, 7, 8, 9

Algorithm of quick sort

Step1: Choose a pivot element.

Step2: Partition of the given list/array about the pivot element.

Step3: Passing these smaller arrays to the recursive calls.

We will use two functions to implement this sorting algorithm namely partition() and quick_sort(). The quick_sort() will first call the partition() function on the given array and then call itself recursively on those divided parts of the array.

Python code

# CODE BY COPYASSIGNMENT

# The partition function takes last element as pivot, places 
# the pivot element at its correct position in sorted 
# array, and places all smaller (smaller than pivot) 
# to left of pivot and all greater elements to right 
# of pivot 
def partition(arr,low,high): 
	i = ( low-1 )		 # index of smaller element 
	pivot = arr[high]	 # pivot 

	for j in range(low , high): 

		# If current element is smaller than the pivot 
		if arr[j] < pivot: 
		
			# increment index of smaller element 
			i = i+1
			arr[i],arr[j] = arr[j],arr[i] 

	arr[i+1],arr[high] = arr[high],arr[i+1] 
	return ( i+1 ) 

# Quick sort function
def quickSort(arr,low,high): 
	if low < high: 

		# pi is partitioning index, arr[p] is now 
		# at right place 
		pi = partition(arr,low,high) 

		# Separately sort elements before 
		# partition and after partition 
		quickSort(arr, low, pi-1) 
		quickSort(arr, pi+1, high) 

# Driver code 
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("Sorted array is:") 
for i in range(n): 
	print ("%d" %arr[i])

Output



Time Complexity of Quick Sort Algorithm

Time Complexity: In programming Time Complexity is defined as the total time taken by a program to execute and completely run all its functions. When it comes to calculating Time Complexity we consider three main factors:

  • Worst case: The worst-case scenario occurs when one of the partitioned arrays is of size n-1. This only happens when the pivot element is the largest of the smallest element from the list. In this case, the time complexity is O(n^2).
  • Best case: The best-case scenario occurs when the divided partitions are equally balanced or differ by just one. The first case occurs when the pivot element is right in the middle of the list, then each partition has (n-1)/2 elements. The second case occurs when one partition of the subarray has an even number of elements and the other has an odd number of elements. In either case, there are utmost n/2 elements in a partition. So the best case time complexity of the quick sort algorithm comes out to be O(n(logn)).
  • Average case: The average time complexity of the quick sort algorithm is also O(n(logn)).   

Space complexity of Quick Sort Algorithm

Space Complexity: In programming, space complexity is defined as the memory space occupied by the program to run and execute all its functions. Similar to the time complexity there are three cases to consider while evaluating the space complexity:

  • Worst case: The worst-case space complexity of the quicksort algorithm is O(n).
  • Best case: The best-case space complexity of the quicksort algorithm is O(logn).
  • Average case: Similarly to the best-case space complexity, the average case space complexity of the quicksort algorithm is also O(logn).

In-place sorting algorithm?

Yes, quick sort is an in-place sorting algorithm as it does not require any other data structure like another array to perform its operations. Furthermore, it does not create any copies of its subarrays.

Stable sorting algorithm?

No, quick sort is an unstable sorting algorithm. A stable sorting algorithm is one in which the same elements appear at the same relative position in the sorted array as they appeared in the given initial unsorted array. Quick sort algorithm does not guarantee the maintenance of this relative order.

Adaptive sorting algorithm?

As the time complexity of the quick sort depends on the initial input sequence, so yes quick sort is an adaptive sorting algorithm just like insertion and bubble sort.

Properties

  1. It uses the principle of divide and conquer.
  2. It does not require any extra space to perform its operations.
  3. Being tail-recursive there is room for optimization.
  4. It is a chase friendly sorting algorithm.

Applications of quick sort

  1. Whenever users don’t need a stable sorting algorithm they prefer quicksort.
  2. The divide and conquer approach enables the use of parallelization.
  3. In the problem of separating the k largest and smallest elements, we use this algorithm.

Thanks for reading my post.

Comment if you have any queries or if you found something wrong in the post or on our website.

Keep learning


Also Read:


Selection Sort Algorithm In Data Structures and Algorithms using Python

Introduction to Searching Algorithms: Linear Search Algorithm

Bubble Sort Algorithm In Data Structures & Algorithms using Python

Merge Sort Algorithm in Python

Binary Search in python

Linear Search Python

Sorting Algorithms and Searching Algorithms in Python


Share:

Author: Umang Aggarwal