C++: Quick sort

Abstract

This article aims to record how to code for quick sort algorithm with C++. Although a sort function has been provided in STL library, it is still useful to understand how to achieve the sort algorithm with basic loops.

Principle

To understand the quick sort easily, visit the website https://visualgo.net/.

C++ Code

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

void quick_sort(vector<int> *serial, int left_pos, int right_pos);

int main(int argc, char* argv[])
{
    vector<int> serial;
    int temp = 0;

    //Hint sentence to ask user input numbers.
    cout << "Please input numbers with space to seperate and finished with any non-number character:" << endl;

    //Use a vector as dynamic array to store numbers.
    while(cin >> temp) serial.push_back(temp);

    //Call quick_sort function.
    quick_sort(&serial, 0, serial.size()-1);

    //Print the result.
    cout << endl << "From min to max:" << endl;
    for(int i = 0; i < serial.size(); i++)
        cout << serial[i] << " ";
    cout << endl;

    return 0;
}

void quick_sort(vector<int> *serial, int left, int right)
{
    int temp = 0, base, base_pos;
    int left_pos, right_pos;

    //Flag and condition for recursive finished.
    if(left > right) return;

    //The first number on the left is the base number by default.
    base = (*serial)[left];
    base_pos = left;

    //Specifies the numbers at both ends of this sort.
    left_pos = left;
    right_pos = right;

    //When the left and right are not search to the same number.
    while(left_pos != right_pos)
    {
        //Search from right one by one until the searched number < base number.
        while(((*serial)[right_pos] >= base) && (left_pos < right_pos)) right_pos--;
        //Search from left one by one until the searched number > base number.
        while(((*serial)[left_pos] <= base) && (left_pos < right_pos)) left_pos++;

        //Swap the two searched number.
        if(left_pos != right_pos)
        {
            temp = (*serial)[left_pos];
            (*serial)[left_pos] = (*serial)[right_pos];
            (*serial)[right_pos] = temp;
        }
    }

    /* When it become the same number for searching from both sides, swap the current 
    number and the base number to confirm the position of base number. */
    (*serial)[base_pos] = (*serial)[left_pos];
    (*serial)[left_pos] = base;

    //Recursive to continue sorting for the left and right parts.
    quick_sort(serial, left, left_pos-1);
    quick_sort(serial, left_pos+1, right);
}