1.
Introduction
2.
Real-life Example Based on Quick Sort
2.1.
Quick Sort Algorithm
2.1.1.
How It Works
3.
Example
3.1.
C
4.
How to Choose Pivot in Quick Sort Algorithm?
4.1.
First Element as Pivot
4.2.
Last Element as Pivot
4.3.
Random Element as Pivot
4.4.
Median as Pivot
4.5.
Median-of-Medians as Pivot
4.6.
Selecting a pivot is a trade-off between simplicity and efficiency
4.7.
Efficiency
4.8.
In-place Sorting
4.9.
Divide & Conquer
4.10.
Easily Implementable
4.11.
Good Average Case
4.12.
5.
5.1.
Worst-Case Performance
5.2.
Sensitive to Pivot Choice
5.3.
Not Stable
5.4.
5.5.
Inconsistent Performance
5.6.
Not Always the Best for Small Lists
6.
6.1.
Why is quick sort faster than other sorting algorithms like bubble sort?
6.2.
Can quick sort be used for sorting linked lists?
6.3.
How can the worst-case performance of quick sort be avoided?
7.
Conclusion
Last Updated: Apr 6, 2024
Medium

Quick Sort Program in C

Rinki Deka
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

Introduction

Quick sorting is a method used to arrange a list of elements in order, whether it's numbers, words, or even dates on a calendar. Itâ€™s one of the famous algorithms and widely used in programming due to its efficiency.This method is super useful in programing for tasks like data analysis, where sorting through massive amounts of information quickly is crucial.

In this article, we'll learn how quick sorting works, its real-life applications, and how to implement it in C programming.

Real-life Example Based on Quick Sort

Imagine you're in charge of organizing books in a library. You have a big pile, and you need to put them in order on the shelves. You pick a book from the middle and start comparing other books to it. Books that should come before it go on one side, and those that come after go on the other. You then pick another book from each smaller pile and do the same thing again and again until all books are neatly arranged. This is similar to how the quick sort algorithm works. It picks a 'pivot' item, sorts items around it, and keeps doing this in smaller groups until everything is in order. This method is not just for books but is used in computer programs to sort lists of data, making it easier to find and use the information they contain.

Quick Sort Algorithm

Quick sort is a popular sorting method in computer programming. It's known for its efficiency and is widely used in various applications. The algorithm follows a simple process of picking a single element from the list as a pivot and then arranging the rest of the elements around this pivot so that elements on one side are smaller and on the other side are larger. This process, called partitioning, is then recursively applied to the smaller lists on either side of the pivot.

How It Works

• Pivot Selection: The first step is to choose a pivot element. This can be any element from the list, such as the first, last, or a random element.

• Partitioning: Rearrange the list so that all elements less than the pivot come before it and all elements greater come after it. After this step, the pivot is in its final position.

• Recursive Sort: Apply the same steps to the sub-lists created on either side of the pivot. This process is repeated until the sub-lists contain only one element and no further partitioning is possible.

• Combining: Since the algorithm works by modifying the list in place, no combining step is needed. The list becomes fully sorted once all the recursive calls are completed.

The efficiency of quick sort lies in its divide-and-conquer approach, which breaks down a big problem (sorting a large list) into smaller problems (sorting smaller sub-lists) and solves each efficiently.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

This example will sort an array of integers using quick sort. It includes functions for partitioning the array and for the recursive quick sort algorithm.

• C

C

``/******************************************************************************Welcome to GDB Online.GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.Code, Compile, Run and Debug online from anywhere in world.*******************************************************************************/#include <stdio.h>// Function to swap two elementsvoid swap(int* a, int* b) {    int t = *a;    *a = *b;    *b = t;}// This function takes the last element as pivot, places// the pivot element at its correct position in sorted array,// and places all smaller elements to left of pivot and all// greater elements to right of pivot.int partition(int arr[], int low, int high) {    int pivot = arr[high];    // pivot    int i = (low - 1);  // Index of smaller element    for (int j = low; j <= high - 1; j++) {        // If current element is smaller than the pivot        if (arr[j] < pivot) {            i++;    // increment index of smaller element            swap(&arr[i], &arr[j]);        }    }    swap(&arr[i + 1], &arr[high]);    return (i + 1);}// The main function that implements QuickSort// arr[] --> Array to be sorted,// low  --> Starting index,// high  --> Ending indexvoid quickSort(int arr[], int low, int high) {    if (low < high) {        // pi is partitioning index, arr[p] is now        // at right place        int pi = partition(arr, low, high);        // Separately sort elements before        // partition and after partition        quickSort(arr, low, pi - 1);        quickSort(arr, pi + 1, high);    }}// Function to print an arrayvoid printArray(int arr[], int size) {    int i;    for (i = 0; i < size; i++)        printf("%d ", arr[i]);    printf("\n");}// Driver program to test above functionsint main() {    int arr[] = {10, 7, 8, 9, 1, 5};    int n = sizeof(arr) / sizeof(arr[0]);    quickSort(arr, 0, n - 1);    printf("Sorted array: \n");    printArray(arr, n);    return 0;}``

Output

``````^ASorted array:
1 5 7 8 9 10 ``````

This code snippet begins by defining a swap function to exchange the values of two integer variables. The partition function then arranges elements around the pivot, which is chosen to be the last element of the array segment being sorted. The quickSort function implements the recursive quick sort algorithm, calling itself for the sub-arrays before and after the pivot's final position. Finally, printArray displays the sorted array.

How to Choose Pivot in Quick Sort Algorithm?

Choosing the right pivot in quick sort is crucial because it can significantly affect the algorithm's efficiency. The pivot is the element around which the list is partitioned; hence, its position can make the sorting process faster or slower. There are several strategies to pick a pivot:

First Element as Pivot

This is the simplest method where the first element of the array or sub-array is chosen as the pivot. While easy to implement, it's not always the most efficient, especially if the array is already or nearly sorted.

Last Element as Pivot

Similar to the first element, but the last element of the array or sub-array is chosen. This method has similar pros and cons to using the first element as the pivot.

Random Element as Pivot

Selecting a random element as the pivot can often help avoid the worst-case performance of quick sort on nearly sorted arrays. It's more unpredictable but tends to work well on average.

Median as Pivot

This approach involves choosing the median of the first, last, and middle elements of the array or sub-array as the pivot. It's a more sophisticated method that can lead to better performance by aiming for a pivot that's closer to the actual median of the values.

Median-of-Medians as Pivot

This advanced technique is used to find an approximate median as the pivot, ensuring that the partitions are reasonably balanced. While effective, it's more complex to implement and typically used in specialized cases.

Selecting a pivot is a trade-off between simplicity and efficiency

For most practical applications, choosing a random element or the median of the first, last, and middle elements provides a good balance.Advantages of Quick Sort Algorithm

Efficiency

Quick sort is known for its speed, especially on large lists. It can sort a big number of elements much faster than other simple sorting algorithms like bubble sort or insertion sort.

In-place Sorting

It doesn't require much additional space to perform the sorting. This means it modifies the input list directly, saving memory which makes it a good choice for systems with limited space.

Divide & Conquer

This strategy breaks down a big problem (sorting the entire list) into smaller problems (sorting smaller sub-lists), solving them individually, and then combining the results. This approach is usually very efficient.

Easily Implementable

Quick sort can be implemented easily in various programming languages, making it a versatile tool for developers.

Good Average Case

While the worst-case performance (O(nÂ²)) happens on specific list orders, in the average and best cases, quick sort runs in O(n log n) time, which is highly efficient.

With slight modifications, quick sort can be adapted to sort lists of complex objects, handle duplicates more efficiently, or even parallelize the sorting process to take advantage of multi-core processors.

Worst-Case Performance

In the worst-case scenario, such as when the list is already sorted or nearly sorted, and the pivot selection is unfortunate, quick sort can degrade to O(nÂ²) performance, which is much slower compared to other efficient sorting algorithms like merge sort.

Sensitive to Pivot Choice

The efficiency of quick sort heavily depends on the choice of the pivot. An unfortunate choice can lead to unbalanced partitions, resulting in decreased performance.

Not Stable

Quick sort is not a stable sort, meaning that equal elements might not retain their original order in the sorted list. This could be problematic in certain applications where the order of equal elements is important.

The algorithm uses recursion to sort the sub-lists. Deep recursion can lead to a significant amount of overhead and, in extreme cases, can cause a stack overflow error.

Inconsistent Performance

The performance of quick sort can vary significantly depending on the input data and the method used for selecting the pivot, making it less predictable than some other sorting algorithms.

Not Always the Best for Small Lists

For very small lists, simpler sorting algorithms like insertion sort might be more efficient due to lower overhead.

Why is quick sort faster than other sorting algorithms like bubble sort?

Quick sort is generally faster because it uses a divide-and-conquer approach to sort subsets of the list independently, which significantly reduces the total number of comparisons and swaps needed.

Can quick sort be used for sorting linked lists?

Yes, quick sort can be adapted to sort linked lists. The main difference in implementation involves the way elements are swapped and partitioned, as linked lists allow for efficient insertion and deletion operations.

How can the worst-case performance of quick sort be avoided?

The worst-case performance of quick sort can often be mitigated by choosing the pivot more carefully, such as using the median-of-three method or selecting a random pivot, which helps ensure more balanced partitions.

Conclusion

In this article, we talked about the quick sort algorithm in detail. We started with real-life examples to understand its concept, we moved on to discussing the algorithm's steps, implementing it in C, and how to choose an effective pivot. We also looked at the significant advantages that make quick sort a preferred choice in programming, despite its disadvantages, which include potential inefficiency with unfortunate pivot choices and the algorithm's non-stable nature.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems