Algorithms – Sorting – Quick Sort – Source Code

This article provides the source code for the Quick Sort algorithm discussed in Algorithms – Sorting – Quick Sort post.

The source code is in C++ language and was verified to be working as expected on a x86_64 (64 bit) machine running Ubuntu 11.04.

Source Code:

/*
 * Quick_Sort.cpp
 *
 *  Created on: 23-Jul-2011
 *      Author: Santhosh
 */

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

void sort(int *a, int n);
void quicksort(int *a, int left, int right);
int partition(int *a, int left, int right);
void swap(int *a, int sourcepos, int destpos);
void displaydata(int *a, int n);
int readInputFromFile(int *input);

/* == FUNCTION =================================================================
 *  NAME       : main
 *
 *  PARAMETERS : none
 *
 *  DESCRIPTION:
 *      The main method that reads the input from a file and then invokes
 *  the quick sort algorithm to sort the data. The input data is displayed on
 *  terminal before and after sorting the data.
 * =============================================================================
 */

int main() {
    const int size = 50;
    int input[size];
    cout << "Reading input: ";
    int n = readInputFromFile(input);
    if (n > 0) {
        cout << "Success (" << n << " items)!" << endl;
    } else {
        cout << "Zero items!" << endl;
        exit(1);
    }
    cout << "Before sorting: " << endl;
    displaydata(input, n);
    sort(input, n);
    cout << "After sorting: " << endl;
    displaydata(input, n);
    return 0;
}

/* == FUNCTION =================================================================
 *  NAME       : sort
 *
 *  PARAMETERS :
 *      input  : an integer array to be sorted.
 *          n  : size of the array.
 *
 *  DESCRIPTION:
 *      This method invokes the quicksort method with right values.
 * =============================================================================
 */

void sort(int *a, int n) {
    quicksort(a, 0, n - 1);
}

/* == FUNCTION =================================================================
 *  NAME       : quicksort
 *
 *  PARAMETERS :
 *      input  : an integer array to be sorted.
 *       left  : lower index of the array
 *      right  : higher index of the array
 *
 *  DESCRIPTION:
 *      This method sorts the contents of the array pointed by the 'input'
 *  variable in ascending order utilzing the quick sort algorithm (recursively).
 * =============================================================================
 */

void quicksort(int *a, int left, int right) {
    if (left < right) {
        int pivotpos = partition(a, left, right);
        quicksort(a, left, pivotpos - 1);
        quicksort(a, pivotpos + 1, right);
    }
}

/* == FUNCTION =================================================================
 *  NAME       : partition
 *
 *  PARAMETERS :
 *      input  : an integer array to be sorted.
 *       left  : lower index of the array
 *      right  : higher index of the array
 *
 *  DESCRIPTION:
 *      In liner time, this method groups the subarray (a[left, right]) around a
 *  pivot element (initially chosen as the left most element of the subarray)
 *  by sorting pivot into its proper position, indicated by 'store', within the
 *  subarray and ensuring that all the elements of the subarray, a[left, store]
 *  are less than or equal to pivot and all element of the subarray,
 *  a[store+1, right] are greater than pivot.
 * =============================================================================
 */

int partition(int *a, int left, int right) {

    int pivotpos = left; // Consider the left most element as pivot!
    int store = left; // Set store to point to the left most element

    // Move the pivot to the end of the subarray, a[left, right].
    swap(a, pivotpos, right);

    // All values <= pivot are moved to the front of the subarray, a[left+right]
    // and pivot inserted just after them.
    for (int i = left; i < right; i++) { // i should run from left to right-1
        if (*(a + i) <= *(a + right)) { // because a[right] = a[pivotpos]
            swap(a, i, store);
            store++;
        }
    }

    swap(a, store, right); // Move pivot into its proper position! Important!

    return store; // Return the position of the pivot!
}

/* == FUNCTION =================================================================
 *  NAME       : displayArray
 *
 *  PARAMETERS :
 *      input  : an integer array whose elements are to be displayed.
 *       size  : size of the array.
 *
 *  DESCRIPTION:
 *      This method reads the input file for space separated integer values and
 *  updates the 'input' array (passed as a parameter).
 * =============================================================================
 */

void displaydata(int *a, int n) {
    for (int i = 0; i < n; i++)
        cout << "\t" << *(a + i);
    cout << endl;
}

/* == FUNCTION =================================================================
 *  NAME       : displayArray
 *
 *  PARAMETERS :
 *           a : pointer to the integer array whose elements are to be swapped.
 *   sourcepos : index of the element to be swapped.
 *     destpos : index of the element to be swapped.
 *
 *  DESCRIPTION:
 *      This method swaps the contents of two location within an array.
 * =============================================================================
 */

void swap(int *a, int sourcepos, int destpos) {
    int temp = *(a + sourcepos);
    *(a + sourcepos) = *(a + destpos);
    *(a + destpos) = temp;
}

/* == FUNCTION =================================================================
 *  NAME       : readInputFromFile
 *
 *  PARAMETERS :
 *      input  : an integer array which should be filled with elements that are
 *               read from the input file.
 *
 *  RETURN     :
 *      count  : an integer whose value signifies the actual length of the
 *               array.
 *
 *  DESCRIPTION:
 *      This method reads the input file for space separated integer values and
 *  updates the 'input' array (passed as a parameter).
 * =============================================================================
 */

int readInputFromFile(int *input) {
    const char* inputFilePath = "input.txt";
    ifstream in(inputFilePath);
    if (in.fail()) {
        cerr << "Failed to open the file: " << inputFilePath << "!" << endl;
        exit(1);
    }
    int value, count = 0;
    while (in >> value) {
        if (in.fail()) {
            cerr << "Input source failed after reading " << count << " items!"
                    << endl;
            in.close();
            exit(1);
        } else {
            *(input + count) = value;
            count++;
        }
    }
    in.close();
    return count;
}
Advertisements

3 thoughts on “Algorithms – Sorting – Quick Sort – Source Code

    1. Thank you Arjun for taking the time to read the blog post and share your suggestions. I had used ‘sourcecode’ earlier and was not impressed with the output. Will give it a try again.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s