C++ Example – Quick Sort Algorithm

August 25, 2016 admin C++ 0

Basic Idea

Pick one element in the array, which will be the pivot.
Make one pass through the array, called a partition step, re-arranging the entries so that:
- entries smaller than the pivot are to the left of the pivot.
- entries larger than the pivot are to the right

Recursively apply quicksort to the part of the array that is to the left of the pivot, and to the part on its right.

No merge step, at the end all the elements are in the proper order

In this lesson we will learn how to write a source code in C++ programming language for doing simple quick sort using array in ascending order.

Quick Sort Example :

/**
Quick Sort Algorithm C++ Example by Codebind.com
*/
#include <iostream>

void PrintArray(int *array, int n) {
  for (int i = 0; i < n; ++i)
    std::cout << array[i] << " " << std::flush;
  std::cout << std::endl;
}

inline void Swap(int &a, int &b){
    int k = a;
    a = b;
    b = k;
}

//reload rand to produce random number in a fixed range
inline int rand(int p, int q){
    int size = q - p + 1;
//    srand(time(NULL));
    return (p + rand() % size);
}
int Partition(int arr[], int lo, int hi){
    //produce ramdom subscript
    int t = rand(lo, hi);
    Swap(arr[t], arr[hi]);

    int index = lo - 1;
    int key = arr[hi];
    for(int i = lo ; i < hi; i++){
        if(arr[i] <= key)
            Swap(arr[++index], arr[i]);
    }
    Swap(arr[++index], arr[hi]);
    return index;
}
void QuickSortHelper(int arr[], int lo, int hi){
    if(lo < hi){
        int index = Partition(arr, lo, hi);
        QuickSortHelper(arr, lo, index-1);
        QuickSortHelper(arr, index+1, hi);
    }
}

void QuickSort(int arr[], int arr_size){
    QuickSortHelper(arr, 0, arr_size-1);
}


int main() {
  int array[] = {94, 42, 50, 95, 333, 65, 54, 456, 1, 1234};
  int n = sizeof(array)/sizeof(array[0]);

  std::cout << "Before Quick Sort :" << std::endl;
  PrintArray(array, n);

  QuickSort(array, n);

  std::cout << "After Quick Sort :" << std::endl;
  PrintArray(array, n);
  return (0);
}


/*
OUTPUT
Before Quick Sort :
94 42 50 95 333 65 54 456 1 2325
After Quick Sort :
1 42 50 54 65 94 95 333 456 2325
*/