C++ Program to Perform Quick Sort on Large Number of Elements

The quicksort technique is done by separating the list into two parts. Initially a pivot element is chosen by partitioning algorithm. The left part of the pivot holds the smaller values than pivot, and right part holds the larger value. After partitioning, each separate lists are partitioned using same procedure.

Here we are considering a large array (nearly 100 elements) to sort. We are taking some numbers then shuffling them in randomized order to make them unsorted. Then sort using quicksort technique.

The complexity of Quicksort Technique

• Time Complexity − O(n log n) for best case and average case, O(n²) for worst case.

• Space Complexity − O(log n)

Input − The unsorted list: 90 45 22 11 22 50
Output − Array after Sorting: 11 22 22 45 50 90

Algorithm

partition(array, lower, upper)

Input − The data set array, lower boundary and upper boundary

Output − Pivot in the correct position

Begin    pivot := array[upper]    i := lower – 1    for j in range lower to higher, do       if array[j] < pivot, then          exchange the values of array[i] and array[j]          i := i + 1    done    exchange the values of array[upper] and array[i + 1]    return i + 1 End

quickSort(array, left, right)

Input − An array of data, and lower and upper bound of the array

Output − The sorted Array

Begin    if lower < right then    q = partition(array, left, right).    quickSort(array, left, q-1)    quickSort(array, q+1, right) End

Example Code 

 Live Demo

#include<iostream> #include<cstdlib> #include<ctime> #define MAX 100 using namespace std; void random_shuffle(int arr[]) { //function to shuffle the array elements into random positions    srand(time(NULL));    for (int i = MAX - 1; i > 0; i--) {       int j = rand()%(i + 1);       int temp = arr[i];       arr[i] = arr[j];       arr[j] = temp;    } } int partion(int arr[], int p, int r) {    int pivot = arr[r]; //last item as pivot    int i = p - 1;    for (int j = p; j < r; j++) {       if (arr[j] < pivot) {          i++;          swap(arr[i], arr[j]);       }    }    swap(arr[i+1], arr[r]);    return i + 1; } void quick_sort(int arr[], int p, int q) { //recursively sort the list    int j;    if (p < q) {       j = partion(arr, p, q);       quick_sort(arr, p, j - 1);       quick_sort(arr, j + 1, q);    } } int main() {    int i;    int arr[MAX];    for (i = 0;i < MAX;i++)    arr[i] = i + 1;    random_shuffle(arr); //To randomize the array    quick_sort(arr, 0, MAX-1); //sort the elements of array    for (i = 0; i < MAX;i++)       cout << arr[i] << " ";    cout << endl;    return 0; }

Output

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100