# 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:

1. Select a pivot element from the array.
2. Initialize two pointers, `left` and `right`, at the beginning and end of the array, respectively.
3. 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`.
4. 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:

1. Initialize `left` to 0 and `right` to 7.
2. 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--;
}
}

``````