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.
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
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 Array\n";
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).
82.9%
of professionals don't believe their degree can help them get ahead at work.
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.
Why is Quick Sort called quick?
What is a pivot in Quick Sort?
Is Quick Sort stable?
What is the simplest sorting algorithm?
When should you use quicksort?
Updated on July 29, 2024