Quick Sort in Data Structures

Amit Kumar Ghosh 26 min read

15 Jun 2023

Intermediate

648 Views

Introduction

Are you looking to become a coding master? If so, then understanding the basics of data structure is essential. It's important to learn how different algorithms can be applied to sorting and searching for your data. One such algorithm is Quick Sort, an efficient comparison-based sorting technique that optimizes the storage capacity of computers by rearranging elements in lists with respect to some order. In this article, we'll take a closer look at exactly what quick sort in data structure is, its benefits and drawbacks, as well as practical applications you can use it for. So whether you're just beginning your journey into computer science or looking to brush up on your current skillset, let's jump right into exploring quick sort

What is Quick Sort Algorithm in Data Structure

Quick sort is a highly efficient, comparison-based sorting algorithm that follows the divide-and-conquer strategy. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted, and the process continues until the entire array is sorted.

Working of Quick Sort Algorithm

Quick sort is a popular sorting algorithm that follows the divide-and-conquer approach. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays based on whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's how the Quicksort algorithm works:

Pivot Selection: Choose a pivot element from the array. There are various ways to choose a pivot, such as selecting the first, last, or middle element. The choice of pivot can affect the efficiency of the algorithm, but for simplicity, let's assume we select the last element as the pivot.
Partitioning: Rearrange the array such that all elements less than the pivot are placed before it, and all elements greater than the pivot are placed after it. This step is also known as partitioning. To do this, maintain two pointers, i and j, initially pointing to the first element of the array.

Iterate j from the first element to the second-to-last element of the array.
If arr[j] is less than the pivot, swap arr[j] with arr[i] and increment i.
After the iteration, swap the pivot element (arr[last]) with arr[i]. Now, the pivot element is in its sorted position in the array.
All elements to the left of the pivot (from index 0 to i-1) are smaller than the pivot, and all elements to the right (from index i+1 to the last element) are greater than the pivot.

Recursive Sort: Recursively apply the above two steps to the sub-arrays on both sides of the pivot (i.e., the elements to the left and right of the pivot) until the sub-arrays contain only one element or are empty.

Apply the Quicksort algorithm to the sub-array from index 0 to i-1 (left of the pivot).
Apply the Quicksort algorithm to the sub-array from index i+1 to the last element (right of the pivot).

Combine: The sub-arrays are now sorted. The elements on the left of the pivot are all less than the pivot, and the elements on the right are all greater than the pivot. As a result, the entire array is sorted.
Termination: The recursion terminates when the sub-arrays have zero or one element, as they are already sorted by definition.

This process of recursive partitioning and sorting the sub-arrays continues until the entire array is sorted. The average and best-case time complexity of Quicksort is O(n log n), where n is the number of elements in the array. However, in the worst case, when the pivot is consistently chosen poorly (e.g., the array is already sorted), the time complexity can degrade to O(n^2). To mitigate this, various optimizations, such as choosing a random pivot or using the "median-of-three" method, can be employed.

Quick sort complexity

There are two types of quick sort complexity algorithm

Time complexity- the worst-case time complexity of the quicksort algorithm is O(n^2), where n is the number of elements to be sorted. This can happen when the pivot element is either the smallest or largest element in the array, which causes the partitioning to result in unbalanced subarrays. However, in the average case, the time complexity of quicksort is O(nlogn), which is very efficient. In fact, quicksort is one of the fastest sorting algorithms in practice and is widely used in many applications.
Space complexity- The space complexity of quicksort depends on the implementation of the algorithm. In the standard recursive implementation, the space complexity is O(log n) on average, where n is the number of elements to be sorted. This is because quick sort uses a recursive call stack to keep track of the sub-arrays to be sorted. The maximum depth of the call stack is determined by the number of times the algorithm partitions the input array, which is proportional to the number of times the pivot element is chosen. On average, the number of times the pivot element is chosen is proportional to the logarithm of n, so the space complexity is O(log n). However, in the worst-case scenario, when the pivot is chosen poorly (e.g., if the input array is already sorted), quicksort can have a worst-case space complexity of O(n). This is because the algorithm will make n recursive calls, one for each element in the input array. In practice, quicksort is usually implemented with optimizations to reduce the worst-case space complexity, such as limiting the depth of the recursive calls or using an iterative implementation.

Quick sort application

Here are some Quick Sort Applications:

Sorting: Quick sort is primarily used for sorting data. It is a very efficient algorithm and is faster than most other sorting algorithms.
Searching: Quick sort can be used in searching algorithms. For example, if the user has an unsorted array and they want to find a specific value, can sort the array using quick sort and then perform a binary search on it.
Numerical analysis: Quick sort can be used in numerical analysis, for example, to sort a large data set of numbers.
Parallel computing: Quick sort is well-suited for parallel computing because it can be easily parallelized. This makes it an ideal choice for distributed computing systems.
Database management: Quick sort can be used in database management systems to sort large amounts of data efficiently. It can also be used in indexing and searching algorithms.

Quick Sort Algorithm

quickSort(array, leftmostIndex, rightmostIndex)
   if (leftmostIndex < rightmostIndex)
     pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
     quickSort(array, leftmostIndex, pivotIndex - 1)
     quickSort(array, pivotIndex, rightmostIndex)
 
 partition(array, leftmostIndex, rightmostIndex)
   set rightmostIndex as pivotIndex
   storeIndex <- leftmostIndex - 1
   for i <- leftmostIndex + 1 to rightmostIndex
   if element[i] < pivotElement
     swap element[i] and element[storeIndex]
     storeIndex++
   swap pivotElement and element[storeIndex+1]
 return storeIndex + 1

Implementation of Quick Sort


 /p># Quick sort in Python

 # function to find the partition position
 def partition(array, low, high):
 
   # choose the rightmost element as pivot
   pivot = array[high]
 
   # pointer for greater element
   i = low - 1
 
   # traverse through all elements
   # compare each element with pivot
   for j in range(low, high):
     if array[j] <= pivot:
       # if element smaller than pivot is found
       # swap it with the greater element pointed by i
       i = i + 1
 
       # swapping element at i with element at j
       (array[i], array[j]) = (array[j], array[i])
 
   # swap the pivot element with the greater element specified by i
   (array[i + 1], array[high]) = (array[high], array[i + 1])
 
   # return the position from where partition is done
   return i + 1
 
 # function to perform quicksort
 def quickSort(array, low, high):
   if low < high:
 
     # find pivot element such that
     # element smaller than pivot are on the left
     # element greater than pivot are on the right
     pi = partition(array, low, high)
 
     # recursive call on the left of pivot
     quickSort(array, low, pi - 1)
 
     # recursive call on the right of pivot
     quickSort(array, pi + 1, high)
 
 
 data = [85, 74, 66, 1, 0, 19, 3]
 print("Unsorted Array")
 print(data)
 
 size = len(data)
 
 quickSort(data, 0, size - 1)
 
 print('Sorted Array in Ascending Order:')
 print(data)


 // Quick sort in C++

 #include <iostream>
 using namespace std;
 
 // function to swap elements
 void swap(int *a, int *b) {
   int t = *a;
   *a = *b;
   *b = t;
 }
 
 // function to print the array
 void printArray(int array[], int size) {
   int i;
   for (i = 0; i < size; i++)
     cout << array[i] << " ";
   cout << endl;
 }
 
 // function to rearrange array (find the partition point)
 int partition(int array[], int low, int high) {
 
   // select the rightmost element as pivot
   int pivot = array[high];
 
   // pointer for greater element
   int i = (low - 1);
 
   // traverse each element of the array
   // compare them with the pivot
   for (int j = low; j < high; j++) {
     if (array[j] <= pivot) {
 
       // if element smaller than pivot is found
       // swap it with the greater element pointed by i
       i++;
 
 // Quick sort in Java
 
 import java.util.Arrays;
 
 class Quicksort {
 
   // method to find the partition position
   static int partition(int array[], int low, int high) {
 
     // choose the rightmost element as pivot
     int pivot = array[high];
 
     // pointer for greater element
     int i = (low - 1);
 
     // traverse through all elements
     // compare each element with pivot
     for (int j = low; j < high; j++) {
       if (array[j] <= pivot) {
 
         // if element smaller than pivot is found
         // swap it with the greatr element pointed by i
         i++;
 
         // swapping element at i with element at j
         int temp = array[i];
         array[i] = array[j];
         array[j] = temp;
       }
 
     }
 
     // swapt the pivot element with the greater element specified by i
     int temp = array[i + 1];
     array[i + 1] = array[high];
     array[high] = temp;
 
     // return the position from where partition is done
     return (i + 1);
   }
 
   static void quickSort(int array[], int low, int high) {
     if (low < high) {
 
       // find pivot element such that
       // elements smaller than pivot are on the left
       // elements greater than pivot are on the right
       int pi = partition(array, low, high);
 
       // recursive call on the left of pivot
       quickSort(array, low, pi - 1);
 
       // recursive call on the right of pivot
       quickSort(array, pi + 1, high);
     }
   }
 }
 
 // Main class
 class Main {
   public static void main(String args[]) {
 
     int[] data = { 85, 74, 66, 1, 0, 19, 3 };
     System.out.println("Unsorted Array");
     System.out.println(Arrays.toString(data));
 
     int size = data.length;
 
     // call quicksort() on array data
     Quicksort.quickSort(data, 0, size - 1);
 
     System.out.println("Sorted Array in Ascending Order: ");
     System.out.println(Arrays.toString(data));
   }
 }


       // swap element at i with element at j
       swap(&array[i], &array[j]);
     }
   }
 
   // swap pivot with the greater element at i
   swap(&array[i + 1], &array[high]);
 
   // return the partition point
   return (i + 1);
 }
 
 void quickSort(int array[], int low, int high) {
   if (low < high) {
 
     // find the pivot element such that
     // elements smaller than pivot are on left of pivot
     // elements greater than pivot are on righ of pivot
     int pi = partition(array, low, high);
 
     // recursive call on the left of pivot
     quickSort(array, low, pi - 1);
 
     // recursive call on the right of pivot
     quickSort(array, pi + 1, high);
   }
 }
 
 // Driver code
 int main() {
   int data[] = {85, 74, 66, 1, 0, 19, 3};
   int n = sizeof(data) / sizeof(data[0]);
 
   cout << "Unsorted Array: \n";
   printArray(data, n);
 
   // perform quicksort on data
   quickSort(data, 0, n - 1);
 
   cout << "Sorted array in ascending order: \n";
   printArray(data, n);
 }

Output

Unsorted Array:
85, 74, 66, 1, 0, 19, 3
Sorted array in ascending order:
0, 1, 3, 19, 66, 74, 85

How does QuickSort work?

Choose a pivot: Select an element from the array to serve as the pivot. The pivot selection can vary, but a common approach is to choose the last element in the array.
Partitioning: Reorder the array so that all elements less than the pivot are placed before the pivot, and all elements greater than the pivot are placed after it. After this partitioning step, the pivot will be in its final sorted position.
Recursive sorting: Recursively apply the above two steps to the sub-array on the left of the pivot (elements smaller than the pivot) and the sub-array on the right of the pivot (elements greater than the pivot). This step effectively sorts the two sub-arrays.
Combine the sorted sub-arrays: Once the recursive sorting is complete, the sub-arrays are merged together to obtain the final sorted array. Since the sub-arrays are already sorted, no additional work is needed here.
Repeat: The above steps are applied recursively to smaller sub-arrays until the entire array is sorted.

Quicksort algorithm visualization

This is a step-by-step visual illustration of the Quicksort algorithm using an example array. Let's consider the following array as our initial input:

Step 1:

We choose a pivot element from the array, which can be any element. For this example, let's select the first element, 7, as the pivot.

Step 2:

Next, we partition the array around the pivot, such that all elements smaller than the pivot come before it, and all elements larger than the pivot come after it. During this process, we move the elements accordingly.

After partitioning, the array will look like this:

Step 3:

Now, we recursively apply the Quicksort algorithm to the two sub-arrays created by the partitioning step. We repeat steps 1 and 2 for each sub-array.

Let's focus on the left sub-array: [4, 2, 1, 6, 5, 3]. We choose the first element, 4, as the pivot and perform the partitioning step:

Next, we recursively apply the Quicksort algorithm to this sub-array.

Step 4:

For the left sub-array, we choose 4 as the pivot and partition the array:

Step 5:

Now, we apply Quicksort to the right sub-array, [5, 6]. As there are only two elements, no partitioning is required, and we can consider the array sorted.

Step 6:

At this point, we have sorted the left and right sub-arrays. We combine them with the pivot (4) in the middle to obtain the fully sorted array:

Step 7:

Lastly, we repeat steps 3 to 6 for the right sub-array of the initial array, [7, 8].

We choose 7 as the pivot and perform the partitioning step:

Since the right sub-array contains only two elements, we consider it sorted.

Step 8:

We combine the sorted left sub-array [1, 2, 3, 4, 5, 6], pivot (7), and sorted right sub-array [8] to obtain the final sorted array:

This completes the Quicksort algorithm for the given array.

Advantages of quick sort

Efficiency: Quick sort is known for its efficiency and has an average time complexity of O(n log n), where n represents the number of elements being sorted. In practice, it often outperforms other sorting algorithms like bubble sort or insertion sort, especially when dealing with large data sets.

In-place sorting: Quick sort performs sorting in-place, meaning it doesn't require additional memory to store temporary data or intermediate results. This makes it memory-efficient and well-suited for situations where memory usage is a concern.

Fast average case: Quick sort's average-case time complexity is significantly faster than many other sorting algorithms. It achieves this by dividing the input array into smaller sub-arrays based on a chosen pivot element and recursively sorting those sub-arrays. This "divide and conquer" approach allows quick sort to efficiently handle large data sets.

Good for parallelization: Quick sort can be parallelized easily, taking advantage of multiple processors or computing resources. By splitting the input array into sub-arrays and sorting them concurrently, it can achieve faster sorting times on systems with parallel processing capabilities.

Efficient for large data sets: Quick sort performs well on large data sets and exhibits good scalability. Its average and best-case time complexities make it suitable for sorting large arrays or lists efficiently.

Adaptive and stable: Quick sort is adaptive, meaning it performs well on partially sorted or almost sorted arrays. Additionally, although the standard implementation of quick sort is not stable (i.e., it may change the relative order of equal elements), there are modifications, like the "three-way partitioning" approach, that can be used to make it stable.

Simple implementation: Quick sort's algorithmic logic is relatively straightforward, making it easier to understand and implement compared to some other complex sorting algorithms

Disadvantages of quick sort

Unstable Sorting: Quick sort is an unstable sorting algorithm, meaning that it does not guarantee the relative order of equal elements after the sorting process. If the order of equal elements is important, quick sort may not be suitable.
Worst-case Performance: Although quick sort has an average-case time complexity of O(n log n), its worst-case time complexity is O(n^2). This worst-case scenario occurs when the pivot chosen is either the smallest or largest element in the array, causing unbalanced partitions. This can lead to poor performance on already sorted or nearly sorted data sets.
Dependency on Pivot Selection: The choice of pivot significantly affects the performance of quick sort. If a poorly chosen pivot divides the array into highly imbalanced partitions, the algorithm's efficiency may degrade. This issue is particularly prominent when dealing with already sorted or nearly sorted arrays.
Recursive Overhead: Quick sort heavily relies on recursion to divide the array into subarrays. Recursive function calls consume additional memory and can lead to stack overflow errors when dealing with large data sets. This makes quick sort less suitable for sorting extremely large arrays.
Not Adaptive: Quick sort's performance is not adaptive to the initial order of the elements. It does not take advantage of any pre-existing order or partially sorted input. This means that even if a portion of the array is already sorted, the quick sort will still perform partitioning operations on the entire array.
Inefficient for Small Data Sets: Quick sort has additional overhead in comparison to some simpler sorting algorithms, especially when dealing with small data sets. The recursive nature of quick sort and the constant splitting of the array can be inefficient for sorting small arrays or arrays with a small number of unique elements.

Summary

Overall, quick sort is a powerful data structure algorithm with advantages such as efficiency and versatility. It is an essential tool for developers to have in their belt when dealing with large amounts of data. By taking the time to study and understand its algorithms, the programmer can make use of it to create efficient, complex programs that can save time and accomplish tasks quickly. This article gives you a vast idea about quick sort definition including the benefits of using quick sort in the data structure can be seen in any application where sorting needs to take place, from constructing databases to performing server-related tasks.

01 Beginner

02 Intermediate

03 Advanced

04 Training Programs