Quick Sort in C
Quick Sort is a fast and efficient sorting algorithm based on the divide and conquer technique . In this article, we will learn how the Quick Sort algorithm works, how to choose a pivot, its time and space complexity, and how to implement a Quick Sort program in C.
Quick Sort works by selecting an element from an array as a pivot and partitioning the remaining elements around it. Elements smaller than the pivot are placed on one side, while elements greater than the pivot are placed on the other side.
The two resulting sub-arrays are then partitioned again using the same approach. This process continues until the array is sorted.
What is Quick Sort?
Quick Sort is a comparison-based sorting algorithm that uses the divide and conquer approach. It selects a pivot element and rearranges the array so that smaller elements are placed before the pivot and larger elements are placed after it.
After the partitioning step, the same process is recursively applied to the left and right sub-arrays.
Unlike Merge Sort , Quick Sort generally performs the partitioning in place, although the exact space usage depends on the implementation and pivot selection.
How Does Quick Sort Work?
To understand Quick Sort, let's take an unsorted array and sort it step by step.
An unsorted array contains elements that are not arranged in ascending or descending order. We will use the following array to understand the partitioning process.
How to Choose a Pivot?
Choosing a pivot is an important part of Quick Sort because the quality of the partition affects the performance of the algorithm. Some common ways to choose a pivot are:
Select the first element as the pivot.
Select the last element as the pivot.
Select a random element as the pivot.
Select the median or an approximate median as the pivot.
Step-by-Step Example of Quick Sort
In our example, we will consider the leftmost element as the pivot. The leftmost index is called Start, while the rightmost index is called End.
In the given array:
a[Start] = 35
a[Pivot] = 35
a[End] = 40
Let's represent these positions in the array.
When the pivot is at the left side, the algorithm starts checking elements from the End and moves toward the Start.
The basic conditions are:
-
If the element at End is greater than the pivot, move End one position toward Start.
-
If the element at End is smaller than the pivot, swap the pivot and the element at End.
In Fig 2, a[End] > a[Pivot], so the End position moves one position toward Start.
In Fig 3, a[End] < a[Pivot]. Therefore, the pivot and End elements are swapped.
When the Pivot Moves to the Right
After the swap, the pivot is now positioned toward the right side. The algorithm starts checking elements from Start and moves toward End.
The following conditions are applied:
-
If the element at Start is smaller than the pivot, move Start one position toward End.
-
If the element at Start is greater than the pivot, swap the pivot and Start.
In Fig 4, a[Start] < a[Pivot], so Start moves one position toward End.
Again, a[Start] < a[Pivot], so Start moves another position toward End.
In Fig 6, a[Start] > a[Pivot]. Therefore, the Start element and pivot are swapped.
Continuing the Partition Process
After the swap, the pivot is once again toward the left side. Therefore, the algorithm starts checking from End and moves toward Start.
If the element at End is greater than the pivot, End moves toward Start. If the element is smaller than the pivot, a swap occurs.
In Fig 7, a[End] > a[Pivot], so End moves one position toward Start.
In Fig 8, a[End] < a[Pivot], so the End element and pivot are swapped.
The pivot is now toward the right side again, so the algorithm checks elements from Start toward End.
When a[Start] < a[Pivot], Start moves one position toward End.
At this point, the pivot element 35 has reached its correct position in the array.
The elements on the left side of 35 are smaller than the pivot, while the elements on the right side are greater than the pivot.
Quick Sort now applies the same process separately to the left and right sub-arrays.
After the partitioning and recursive sorting processes are completed, the array becomes sorted.
Quick Sort Pseudocode
The following pseudocode shows the basic structure of the Quick Sort algorithm.
Quick Sort Algorithm
The following steps describe the Quick Sort algorithm:
Choose an element as the pivot.
Partition the array around the pivot.
Place smaller elements on one side of the pivot.
Place larger elements on the other side.
Recursively apply Quick Sort to the left sub-array.
Recursively apply Quick Sort to the right sub-array.
Continue until the sub-arrays contain zero or one element.
Quick Sort Program in C
Here is a simple Quick Sort program in C that demonstrates the implementation of the algorithm.
Output of Quick Sort Program in C
Time Complexity of Quick Sort
The time complexity of Quick Sort depends on how well the pivot divides the array during each partitioning step.
Best Case: The best case occurs when the pivot divides the array into two relatively equal parts at each step. The time complexity is O(n log n).
Average Case: The average time complexity of Quick Sort is O(n log n).
Worst Case: The worst case occurs when the pivot repeatedly produces highly unbalanced partitions, such as when the smallest or largest element is repeatedly selected as the pivot. The time complexity becomes O(n²).
Space Complexity of Quick Sort
Quick Sort is generally considered an in-place sorting algorithm because the partitioning can be performed within the original array. However, recursive calls require additional stack space.
The amount of stack space depends on the partitioning pattern and implementation. With reasonably balanced partitions, the recursion depth can be around O(log n), while highly unbalanced partitions can result in O(n) recursion depth.
Advantages of Quick Sort
-
Quick Sort is generally fast in practice and works efficiently for many types of arrays.
-
It can perform partitioning in place, which reduces the need for additional array storage.
-
Quick Sort has good cache locality when working with arrays.
-
Its average time complexity is O(n log n).
Disadvantages of Quick Sort
-
The worst-case time complexity can become O(n²) when partitions are repeatedly unbalanced.
-
Quick Sort is generally not a stable sorting algorithm.
-
Choosing a poor pivot can significantly reduce performance.
-
The recursive implementation requires additional call-stack space.
When Should You Use Quick Sort?
-
Quick Sort can be useful when you need a fast general-purpose sorting algorithm for arrays.
-
It is useful when in-place sorting is desirable and additional array storage should be minimized.
-
A suitable pivot-selection strategy can help Quick Sort perform efficiently on a wide range of input data.
Quick Sort vs Merge Sort
Both Quick Sort and Merge Sort use the divide and conquer approach, but they work differently.
-
Quick Sort partitions the array around a pivot.
-
Merge Sort divides the array into smaller parts and then merges the sorted parts.
-
Quick Sort generally performs its partitioning in place.
-
Merge Sort generally requires additional memory for merging.
Frequently Asked Questions About Quick Sort
What is Quick Sort?
Quick Sort is a comparison-based sorting algorithm that uses the divide and conquer technique. It selects a pivot and partitions the array around that pivot.
What is a pivot in Quick Sort?
A pivot is an element selected from the array that is used to partition the remaining elements into smaller and larger groups.
What is the average time complexity of Quick Sort?
The average time complexity of Quick Sort is O(n log n).
What is the worst-case time complexity of Quick Sort?
The worst-case time complexity is O(n²). This can happen when the pivot repeatedly creates highly unbalanced partitions.
Is Quick Sort stable?
Standard Quick Sort is generally not a stable sorting algorithm, meaning equal elements do not necessarily retain their original relative order.
Can Quick Sort be implemented in C?
Yes. Quick Sort can be implemented in C using functions for partitioning and recursively sorting the left and right portions of the array.
Conclusion
Quick Sort is an efficient sorting algorithm based on the divide and conquer approach. It selects a pivot, partitions the array around the pivot, and recursively sorts the resulting sub-arrays.
The average time complexity of Quick Sort is O(n log n), while its worst-case time complexity is O(n²). The choice of pivot can have a major effect on its performance.
In this article, we learned how Quick Sort works, how the pivot is selected and used, how the array is partitioned, and how to implement a Quick Sort program in C.
