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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/sorting-algorithms/quick-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.