> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/sorting-algorithms/quick-sort.md).

# Quick sort

{% file src="/files/JgLN0NLruRWyAXege6eO" %}

* Random shuffle is a key for good performance in the quick sort algorithm because it guarantees that the worst case isn't gonna happen(rarely happens). 
* Tuned **quicksort** for <mark style="color:red;">primitive types</mark>;
* Worst Case: Array already sorted takes O(n^2) - imp slide # 18

<details>

<summary><em>Randomized Quick Sort</em> - for Duplicate values takes quadratic time</summary>

```cpp
#include <iostream>
#include <random>
using namespace std;

int partition(int *arr, int s, int e)
{
     int i = s, j = e + 1;
     while (true)
     {
          // find item on left to swap
          while (arr[++i] < arr[s]) {
               if (i == e) break;
          }

          // find item on right to swap
          while (arr[s] < arr[--j]) {
               if (j == s) break;
          }

          // check if pointers cross
          if (i >= j) break;

          swap(arr[i], arr[j]);
     }
     
     swap(arr[s], arr[j]); // swap with partitioning item
     return j;
}

void shuffling(int *arr, int n) {
     for (int i = 0; i < n; i++) {
          std::random_device rd;
          std::uniform_int_distribution<int> key(0, i);
          swap(arr[i], arr[key(rd)]);
     }
}

void quickSort(int *arr, int s, int e) {
     if (s >= e) return;

     int j = partition(arr, s, e);
     quickSort(arr, s, j - 1);
     quickSort(arr, j + 1, e);
}

int main() {
     int arr[] = {3, 2, 5, 1, 4};
     
     shuffling(arr, 5); // shuffle needed for performance guarantee
     
     quickSort(arr, 0, 4);
     
     for (int i = 0; i < 5; i++)
          cout << arr[i] << " ";
}
```

![](/files/pzUXVf22tOgsAQnZckoY)

![](/files/sCI6sxJ8n3uJ8H7iUkrK)

</details>

<details>

<summary>Duplicate keys: <em><mark style="color:blue;"><strong>Dijkstra 3 - Way partitioning Quick Sort</strong></mark></em> -  handle duplicate values in o(nlgn) </summary>

![](/files/UHsR1Pw8aCnlN64s49Qx)

v = arr\[lo] = 'P'&#x20;

![](/files/4KWVdP7LbdR5zxabUVHl)

![](/files/gFVBe2TgikGAZDg1gvR5)

```cpp
#include <iostream>
#include <random>
using namespace std;

void shuffling(int *arr, int n)
{
     for (int i = 0; i < n; i++) {
          std::random_device rd;
          std::uniform_int_distribution<int> key(0, i);
          swap(arr[i], arr[key(rd)]);
     }
}

void quickSort(int *arr, int s, int e) {
     if (s >= e) return;
     
     int it = s, gt = e, i = s;
     int v = arr[s];
     
     while (i <= gt) {
          if (arr[i] < v) swap(arr[i++], arr[it++]);
          else if (arr[i] > v) swap(arr[i], arr[gt--]);
          else i++;
     }

     quickSort(arr, s, it - 1);
     quickSort(arr, gt + 1, e);
}

int main() {
    
     int arr[] = {1, 3, 3, 1, 4, 3};
     shuffling(arr, 6); // shuffle needed for performance guarantee 
     quickSort(arr, 0, 5);
     for (int i = 0; i < 6; i++)
          cout << arr[i] << " ";

}
```

![](/files/lKqNMMARjM2iT9eEiJIY)

<mark style="color:blue;">Bottom line.</mark> Randomized quicksort with 3-way partitioning reduces running time from linearithmic (nlgn) to linear in a broad class of applications.

![](/files/CJW14yapWNw8fcfV3HnV)

</details>

## Time Complexity

* **Best Case:** O(nlog⁡n)
* **Average Case:** O(nlog⁡n)
* **Worst Case:** O(n2) (low probability due to randomization)

Randomization helps ensure that the algorithm performs closer to the average case most of the time, providing reliable performance in practical scenarios.

## <mark style="color:blue;">Find kth-Smallest Element using the QuickSelect Algorithm</mark>

**Description:** Implement a program to find the kth smallest element in an unsorted array efficiently using the QuickSelect algorithm, a quicksort algorithm variation. This algorithm allows for finding the kth smallest element in linear time complexity on average.

```cpp
#include <iostream>
#include <random>
using namespace std;

int partition(int *arr, int s, int e)
{
     int i = s, j = e + 1;
     while (true)
     {
          // find item on left to swap
          while (arr[++i] < arr[s])
          {
               if (i == e)
                    break;
          }

          // find item on right to swap
          while (arr[s] < arr[--j])
          {
               if (j == s)
                    break;
          }

          // check if pointers cross
          if (i >= j)
               break;

          swap(arr[i], arr[j]);
     }
     swap(arr[s], arr[j]); // swap with partitioning item
     return j;
}

void shuffling(int *arr, int n)
{
     for (int i = 0; i < n; i++)
     {
          std::random_device rd;
          std::uniform_int_distribution<int> key(0, i);
          swap(arr[i], arr[key(rd)]);
     }
}

int quickSelect(int *arr, int n, int k)
{
     k -= 1;
     shuffling(arr, n); // shuffle needed for performance guarantee
     int s = 0, e = n - 1;
     while (s < e)
     {
          int j = partition(arr, s, e);
          if (j > k)
               e = j - 1;
          else if (j < k)
               s = j + 1;
          else
               return arr[k];
     }
     return arr[k];
}

int main()
{
     int arr[] = {6, 3, 1, 6, 0, 4, 8};
     int size = 7;
     cout << quickSelect(arr, size, 5) << endl;
}

```

<figure><img src="/files/pzUXVf22tOgsAQnZckoY" alt=""><figcaption></figcaption></figure>