Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Quick sort is a popular sorting alorithm that is relatively easy to understand and implement. In this OpenGenus article, you will learn:

- What is Quick sort?
- How does Quick sort work?
- Implemention of Quick sort using a queue data structure.
- Drawbacks of Quick sort using a queue data structure.

# 1. What is Quick Sort?

The sorting algorithm known as Quick Sort employs a divide-and-conquer tactic. This method is simple to implement into code and efficient in terms of time. Additionally, quick sort uses a lot of space efficiently. These reasons explain why quick sort is a widely used sorting algorithm.

# 2. How does Quick sort Work?

Quick sort essentially works in 3 steps.

**1. Choose a pivot.**

- The pivot is an element which will partition elements that are less than it on the left and greater than it on the right.
- The pivot can be any element in the list, but it is typically either the first, middle, or last element of the list.

**2. Partitioning**

- Rearrange the elements so that the elements less than the pivot will be on the left.
- Rearrange the elements so that the elements greater than the pivot will be on the right.

**3. Recursion**

- The left and right parts of the partition will now be treated as sub-arrays
- Do Steps 1 and 2 on the left and right sub-arrays.

You are finished when the entire array is sorted.

## Here is some psuedo code on how quick sort algorithm will generally run:

```
procedure quicksort(array)
if length(array) <= 1
return array
else
pivot = choosePivot(array)
smaller = []
equal = []
larger = []
for each element in array
if element < pivot
add element to smaller
else if element == pivot
add element to equal
else
add element to larger
return concatenate(quicksort(smaller), equal, quicksort(larger))
procedure choosePivot(array)
// Here, you can choose the pivot using different strategies
// For simplicity, this example uses the last element as the pivot
return last element of array
```

# 3. Implemention of Quick sort using a queue data structure.

There are numerous ways to implement the algorithm known as quicksort. A stack and recursion implementation is typically used to accomplish quick sort, but there are alternative approaches. Today, our attention will be directed towards the queue implementation. The drawbacks of utilizing a quick sort will be covered later.

### Quick Sort Implementation with queue in C++:

```
#include <iostream>
#include <queue>
// Function to swap two elements in an array
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to partition the array around a pivot element
int partition(int *array, int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return i + 1;
}
// Function to sort the array using quicksort with a queue
void quicksort(int *array, int low, int high) {
queue<int> q;
q.push(low);
q.push(high);
while (!q.empty()) {
int low = q.front();
q.pop();
int high = q.front();
q.pop();
int pivotIndex = partition(array, low, high);
//Left Sub-range
if (low < pivotIndex - 1) {
q.push(low);
q.push(pivotIndex - 1);
}
//Right Sub-range
if (pivotIndex + 1 < high) {
q.push(pivotIndex + 1);
q.push(high);
}
}
}
// Function to print the array
void printArray(int *array, int size) {
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
cout << endl;
}
int main() {
int array[] = {5, 3, 2, 1, 4};
int size = sizeof(array) / sizeof(array[0]);
quicksort(array, 0, size - 1);
printArray(array, size);
return 0;
}
```

### Explanation of the Quicksort Function:

**Queue Initialization and Enqueuing Initial Range:**`queue<int> q; q.push(low); q.push(high);`

- This initializes a queue
`q`

and enqueues the initial range`[low, high]`

onto the queue. This range is the whole array to be sorted.

**Iterative Quicksort using a Queue:**`while (!q.empty()) {`

- The sorting process is done iteratively using a
`while`

loop that continues until the queue is empty.

**Dequeuing Current Range:**`int low = q.front(); q.pop(); int high = q.front(); q.pop();`

- Dequeues the front elements of the queue to obtain the current range
`[low, high]`

that needs to be sorted.

**Partitioning the Current Range:**`int pivotIndex = partition(array, low, high);`

- Calls the
`partition`

function to partition current range and determine the pivot index.

**Enqueuing Left and Right Sub-ranges (if needed):**`//Left Sub-range if (low < pivotIndex - 1) { q.push(low); q.push(pivotIndex - 1); } //Right Sub-range if (pivotIndex + 1 < high) { q.push(pivotIndex + 1); q.push(high); }`

- If the left sub-range
`[low, pivotIndex - 1]`

or the right sub-range`[pivotIndex + 1, high]`

is not empty, we enque them into queue. (Keep in mind that this means that we will end up enqueuing all of the elements. We'll discuss the issues with this soon) - This continues until the queue is not empty.

# 4. Drawbacks of Quick sort using a queue data structure

Quick sort typically utilizes a stack and recursion for its algorithm. This results in a comparatively short time complexity, particularly in average case scenarios. This is among the factors that contribute to quick sort's widespread use among developers.

This is comparable to the time complexity of a queue implementation. The reason for this is because the underlying algorithm stays the same. The partition process and swaps don't change based on the implementation, which make up a majority of the time complexity.

## Time Complexity with Stack and Queue implementation:

### Best Case: O(n log(n))

### Average Case: O(n log(n))

### Worst Case: O(n^2)

However, there comes an issue with space complexity. The space complexity of quick sort with a stack implementation is O(log(n)) in average case. This is because, on average, every recursion creates sub arrays that are half the size of the previous array. This makes a recursion tree of O(log(n)) height.

The issue is that, with a queue implementation, you can't sort the array in place like you can with a stack implementation. As we saw earlier, the queue implementation ends up enqueuing all of the elements for the quicksort algorithm. This leads to a O(n) time complexity instead of the O(log(n)) space complexity of stack.

Here's the part which causes the bottleneck in space for the queue implementation:

```
//Left Sub-range
if (low < pivotIndex - 1) {
q.push(low);
q.push(pivotIndex - 1);
}
//Right Sub-range
if (pivotIndex + 1 < high) {
q.push(pivotIndex + 1);
q.push(high);
}
```