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

1. What is Quick sort?
2. How does Quick sort work?
3. Implemention of Quick sort using a queue data structure.
4. 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:

1. 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.

2. 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.

3. 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.

4. Partitioning the Current Range:

   int pivotIndex = partition(array, low, high);
   

• Calls the partition function to partition current range and determine the pivot index.

5. 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);
}

Space complexity of Quick Sort:

Stack: O(log(n))

Queue: O(n)