Quick Sort, a fascinating sorting algorithm in computer science, is like a magician’s trick. It’s a conquer-based sorting algorithm that arranges items in a systematic and efficient manner. Quicksort, the star of the show, is a widely used sorting algorithm that can make n log n comparisons in the average case of sorting an array of n elements. In this article, we’ll unravel the mystery of the Quick Sorting Algorithm step by step. Let’s embark on this intriguing journey.
What is the Quick Sort Algorithm?
Quicksort is a popular and efficient sorting algorithm. It uses the divide-and-conquer approach to sort elements in an array or list.
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure
How Does Quick Sort Work?
In this section, we will see “How does quick sort work”. Let’s discuss each step one by one.
Choose a Pivot: Select an element from the array to be the pivot. The choice of the pivot can vary. It could be the first element, the last element, a random element or the median.
Partition the Array: Rearrange the array so that elements less than the pivot are on the left-hand side and elements greater than the pivot are on the right-hand side. After this step, the pivot is in its final sorted position.
Recursively Apply Quicksort: This process applies the same process to the sub-arrays of elements with smaller values and the sub-arrays of elements with larger values.
How to Implement the Quick Sort Algorithm?
In this section, we will implement the Quick Sort Algorithm in different languages: C++, Java, and Python.
Implementation in C++ language
Program
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[],int low,int high)
{
//choose the pivot
int pivot=arr[high];
//Index of smaller element and Indicate
//the right position of pivot found so far
int i=(low-1);
for(int j=low;j<=high-1;j++)
{
//If current element is smaller than the pivot
if(arr[j]<pivot)
{
//Increment index of smaller element
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[i+1],arr[high]);
return (i+1);
}
// The Quicksort function Implement
void quickSort(int arr[],int low,int high)
{
// when low is less than high
if(low<high)
{
// pi is the partition return index of pivot
int pi=partition(arr,low,high);
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}
int main() {
int arr[]={33,43,5, 343,998};
int n=sizeof(arr)/sizeof(arr[0]);
// Function call
quickSort(arr,0,n-1);
//Print the sorted array
cout<<"Sorted Arrayn";
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
Output
Sorted Array
5 33 43 343 998
Implementation in Java language
Program
class QuickSort {
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void printArr(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void main(String[] args)
{
int arr[]={33,43,5, 343,998};
int N = arr.length;
// Function call
quickSort(arr, 0, N - 1);
System.out.println("Sorted array:");
printArr(arr);
}
}
Output
Sorted array:
5 33 43 343 998
Implementation of Python Quick Sort
Program
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i = i + 1
(array[i], array[j]) = (array[j], array[i])
(array[i + 1], array[high]) = (array[high], array[i + 1])
return i + 1
def quicksort(array, low, high):
if low < high:
pi = partition(array, low, high)
quicksort(array, low, pi - 1)
quicksort(array, pi + 1, high)
# Driver code
if __name__ == '__main__':
array = [33,43,5,343,998];
N = len(array)
# Function call
quicksort(array, 0, N - 1)
print('Sorted array:')
for x in array:
print(x, end=" ")
Output
Sorted array:
5 33 43 343 998
Quicksort Complexity
Quicksort is a very popular sorting algorithm. It is a very useful choice for sorting large datasets and is used in various fields of computer science. Understanding its complexity and having code implemented in multiple programming languages can be valuable for students and professionals, allowing them to leverage Quicksort’s efficiency in their applications.
Time Complexity of Quick Sorts
Average Case : 0(n*log(n))
Worst Case: 0(n^2)
Best Case: 0(n* log(n))
Space Complexity: A quick sort has O(1) auxiliary space and stack space. If we consider the recursive stack space, then it is the worst-case quick sort that could make O(N).
Quicksort Application
In this section, we will discuss the applications of the Quick Sort algorithm. Although the algorithm has many applications, we will discuss some common Ones.
Database Query Processing: In the database, quick sorting is often used for sorting records. It is very efficient and crucial for operations like margin sorting of two datasets, optimizing search queries, and performing range queries.
File Systems: Quick sort is also used to manage files and directories efficiently. Sorting helps in faster retrieval and better organization of files.
Memory Management: Quick sort also can be used in memory management systems to organize and allocate the memory blocks. It is also used for sorting, which helps in quicker access and better management of memory.
What are the Advantages of Quick Sort?
In this section, we will discuss the advantages of Quick Sort. Let’s discuss the quick sort algorithm advantages.
Efficiency: The fast average case performance of 0(n log n).
Cache Friendliness: The quick Sort algorithm is good for cache performance due to the locality of reference.
Simplicity: This algorithm is very simple to implement and understand.
Versatility: Quick Sort algorithm is a very adaptable data structure and customizable pivot selection.
What are the Disadvantages of Quick Sort?
Quick Sort has a worst-case time complexity of 0(N2), which occurs when the pivot is chosen poorly.
It is not good for small data sets
Quick sort is not a stable sort algorithm. It means equal elements may not retain their origin order.
Quick Sort is poorly performed on linked lists compared to arrays due to its need for random access.
Performance can be significantly affected by the choice of pivot, requiring careful selection strategies.
Conclusion
In this article, we learned about the Quick Sort algorithm. It is a highly efficient and widely used sorting algorithm that excels in average case performance with a time complexity of O(log n). It operates using a divide-and-conquer strategy, partitioning the array around a pivot element and recursively sorting the subarrays. We also saw the advantages and disadvantages of the Quick Sort algorithm.
FAQs
Why is Quick Sort called quick?
The quick sort algorithm uses divide and conquer to sort the list or array. However, it is a much faster algorithm, twice or three times faster than any other sorting method.
What is a pivot in Quick Sort?
A pivot element is chosen in the array. The partitioning process will rearrange the array so that elements less than the pivot are on one side and elements greater than the pivot are on the other side.
Is Quick Sort stable?
Quick Sort is not stable by default because it does not necessarily preserve the relative order of equal elements. Developers must be careful when they are implementing quick-sort algorithms.
What is the simplest sorting algorithm?
Bubble Sort is considered the simplest sorting algorithm. It goes through an entire array and compares each element one by one. It then swaps the number and keeps doing this until the list is in ascending or descending order.
When should you use quicksort?
Developers can use Quick Sort, where a stable sort is not needed. Quick sort is a very cache-friendly algorithm as it has a good locality of reference when used for arrays.
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
