Quick sort

4MB

Quicksort.pdf

pdf

• 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 primitive types;

• Worst Case: Array already sorted takes O(n^2) - imp slide # 18

Randomized Quick Sort - for Duplicate values takes quadratic time

#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] << " ";
}

Duplicate keys: Dijkstra 3 - Way partitioning Quick Sort - handle duplicate values in o(nlgn)

v = arr[lo] = 'P'

#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] << " ";

}

Bottom line. Randomized quicksort with 3-way partitioning reduces running time from linearithmic (nlgn) to linear in a broad class of applications.

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.

Find kth-Smallest Element using the QuickSelect Algorithm

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.

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