Quicksort Algorithm And 3-Way QuickSort(With Code in C++/Python/Java)

Quicksort

Quicksort is a divide-and-conquer sorting algorithm that works by selecting a pivot element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then sorted recursively. Quicksort is a comparison-based sort, meaning that it determines the order of elements by comparing them.

Partition Algorithm

The partition algorithm is a key component of the quicksort algorithm. It works by iterating through the elements of the array and partitioning them into two subarrays based on their relationship to the pivot element.

Here is the general outline of the partition algorithm:

Select a pivot element from the array.
Initialize two pointers, left and right, at the beginning and end of the array, respectively.
While left is less than or equal to right, do the following:
1. If the element at left is less than the pivot, increment left.
2. If the element at right is greater than or equal to the pivot, decrement right.
3. If the element at left is greater than or equal to the pivot and the element at right is less than the pivot, swap the elements at left and right and increment left and decrement right.
Return the index of the pivot.

Pseudo Code for recursive QuickSort function:

Here is the pseudocode for the recursive quicksort function:

def quicksort(array):
  if length of array is less than or equal to 1:
    return array
  else:
    pivot = choose pivot element
    left = elements in array less than pivot
    right = elements in array greater than or equal to pivot
    return concatenate(quicksort(left), pivot, quicksort(right))

Pseudo code for partition():

Here is the pseudocode for the partition function:

def partition(array, left, right):
  pivot = choose pivot element
  while left is less than or equal to right:
    if element at left is less than pivot:
      increment left
    if element at right is greater than or equal to pivot:
      decrement right
    if element at left is greater than or equal to pivot and element at right is less than pivot:
      swap elements at left and right
      increment left
      decrement right
  return pivot index

Illustration of partition():

For example, consider the following array and pivot element:

array: [8, 4, 7, 3, 6, 2, 1, 5]
pivot: 5

We can apply the partition algorithm as follows:

Initialize left to 0 and right to 7.
The element at left (8) is greater than the pivot, and the element at right (5) is less than the pivot, so we swap them and increment left and decrement right.

array: [5, 4, 7, 3, 6, 2, 1, 8]
left: 1
right: 6

3. The element at left (4) is less than the pivot, so we increment left.

array: [5, 4, 7, 3, 6, 2, 1, 8]
left: 2
right: 6

4. The element at left (7) is greater than the pivot, and the element at right (2) is less than the pivot, so we swap them and increment left and decrement right.

array: [5, 4, 2, 3, 6, 7, 1, 8]
left: 3
right: 5

5. The element at left (3) is less than the pivot, so we increment left.

array: [5, 4, 2, 3, 6, 7, 1, 8]
left: 4
right: 5

6. The element at left (6) is greater than the pivot, and the element at right (7) is less than the pivot, so we swap them and increment left and decrement right.

array: [5, 4, 2, 3, 7, 6, 1, 8]
left: 5
right: 4

7. left is now greater than right, so we stop the loop and return the index of the pivot (4).

How to pick any element as a pivot

There are several ways to choose the pivot element in the quicksort algorithm:

Choose the first element in the array as the pivot.
Choose the last element in the array as the pivot.
Choose a random element in the array as the pivot.
Choose the median element in the array as the pivot.

Analysis of QuickSort

Quicksort has an average-case time complexity of O(n*log(n)), making it one of the fastest sorting algorithms. However, it has a worst-case time complexity of O(n^2), which can occur if the pivot element is chosen poorly and the array is already partially sorted.

In the best case, quicksort has a time complexity of O(n*log(n)). This occurs when the pivot element is chosen optimally and the array is randomly shuffled.

Worst case

The worst-case time complexity of quicksort is O(n^2), which occurs when the pivot element is chosen poorly and the array is already partially sorted.

Best case

The best-case time complexity of quicksort is O(n*log(n)), which occurs when the pivot element is chosen optimally and the array is randomly shuffled.

Average case

The average-case time complexity of quicksort is O(n*log(n)), making it one of the fastest sorting algorithms.

What is 3-Way QuickSort?

3-way quicksort is a variation of the quicksort algorithm that is optimized for arrays with many duplicate elements. It works by partitioning the array into three subarrays: one for elements less than the pivot, one for elements equal to the pivot, and one for elements greater than the pivot. The subarrays are then sorted recursively.

Here is the implementation of the quicksort algorithm in C++:

#include <iostream>
#include <algorithm>

using namespace std;

int partition(int* array, int left, int right) {
  int pivot = array[left];
  int i = left;
  int j = right;
  while (i <= j) {
    while (array[i] < pivot) {
      i++;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(array[i], array[j]);
      i++;
      j--;
    }
  }
  return i;
}

void quicksort(int* array, int left, int right) {
  if (left >= right) {
    return;
  }
  int pivotIndex = partition(array, left, right);
  quicksort(array, left, pivotIndex - 1);
  quicksort(array, pivotIndex, right);
}

int main() {
  int array[] = {8, 4, 7, 3, 6, 2, 1, 5};
  int n = sizeof(array) / sizeof(int);
  quicksort(array, 0, n - 1);
  for (int i = 0; i < n; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
  return 0;
}

Here is the implementation of the quicksort algorithm in Python:

def partition(array, left, right):
  pivot = array[left]
  i = left
  j = right
  while i <= j:
    while array[i] < pivot:
      i += 1
    while array[j] > pivot:
      j -= 1
    if i <= j:
      array[i], array[j] = array[j], array[i]
      i += 1
      j -= 1
  return i

def quicksort(array, left, right):
  if left >= right:
    return
  pivotIndex = partition(array, left, right)
  quicksort(array, left, pivotIndex - 1)
  quicksort(array, pivotIndex, right)

array = [8, 4, 7, 3, 6, 2, 1, 5]
quicksort(array, 0, len(array) - 1)
print(array)

Here is the implementation of the quicksort algorithm in Java:

import java.util.Arrays;

public class QuickSort {
  public static int partition(int[] array, int left, int right) {
    int pivot = array[left];
    int i = left;
    int j = right;
    while (i <= j) {
      while (array[i] < pivot) {
        i++;
      }
      while (array[j] > pivot) {
        j--;
      }
      if (i <= j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
      }
    }