Quicksort algorithm (deterministic algorithm)

An article by ScienceInsight
Article COD12

Quicksort is a highly efficient sorting algorithm based on the divide-and-conquer principle. It was developed in 1959/1960 by the British computer scientist Tony Hoare. It breaks a list of elements into smaller sublists, sorts these separately, and then recombines them. Here is the exact step-by-step explanation of how it works:

1. Choose the pivot element
The algorithm selects a single element from the list. This element is called the pivot. There are different strategies for selection:
– The first or last element of the list.
– A random element.
– The middle element (median).

2. Partitioning
All other elements of the list are now compared with the pivot element and divided into two new groups:
– Left side: All elements that are less than or equal to the pivot.
– Right side: All elements that are greater than the pivot.
After this step, the pivot element is already in its final, correct position in the fully sorted list.

3. Repeating recursively
The algorithm now turns to the two resulting subgroups (left and right). It treats each group as a new, independent list and applies steps 1 and 2 to them again.

4. Termination condition This loop repeats until the sublists have a length of only one or zero. A list with only one element is automatically sorted. In the end, the entire array is correctly ordered.

In the following example, 4 cards from a Poker deck are sorted according to their ranking:

Code in C++

// Quicksort in C++

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <thread>
#include <chrono>

enum class Suit { Diamond = 0, Heart = 1, Spade = 2, Club = 3 };
enum class Rank {
    Two = 0, Three, Four, Five, Six, Seven, Eight, Nine,
    Ten, Jack, Queen, King, Ace
};

struct Card {
    Suit suit;
    Rank rank;
};

// Comparison function: FIRST by rank, then by suit (both descending)
bool isGreater(const Card& a, const Card& b) {
    if ((int)a.rank != (int)b.rank)
        return (int)a.rank > (int)b.rank;
    return (int)a.suit > (int)b.suit;
}

// QuickSort
void quickSort(std::vector<Card>& cards, int low, int high) {
    if (low >= high) return;
    Card pivot = cards[high];
    int i = low;

    for (int j = low; j < high; ++j) {
        if (isGreater(cards[j], pivot)) {
            std::swap(cards[i], cards[j]);
            ++i;
        }
    }
    std::swap(cards[i], cards[high]);

    quickSort(cards, low, i - 1);
    quickSort(cards, i + 1, high);
}

std::map<std::string, Suit> suits = {
    {"Club", Suit::Club}, {"Spade", Suit::Spade},
    {"Heart", Suit::Heart}, {"Diamond", Suit::Diamond}
};

std::map<std::string, Rank> ranks = {
    {"Ace", Rank::Ace}, {"King", Rank::King}, {"King", Rank::King},
    {"Queen", Rank::Queen}, {"Jack", Rank::Jack}, {"10", Rank::Ten},
    {"9", Rank::Nine}, {"8", Rank::Eight}, {"7", Rank::Seven},
    {"6", Rank::Six}, {"5", Rank::Five}, {"4", Rank::Four},
    {"3", Rank::Three}, {"2", Rank::Two}
};

std::string toString(const Card& c) {
    std::string s, r;

    for (std::map<std::string, Suit>::const_iterator it = suits.begin(); it != suits.end(); ++it) {
        if (it->second == c.suit) {
            s = it->first;
            break;
        }
    }

    for (std::map<std::string, Rank>::const_iterator it = ranks.begin(); it != ranks.end(); ++it) {
        if (it->second == c.rank) {
            r = it->first;
            break;
        }
    }
    return s + " " + r;
}

Card parseCard(const std::string& input) {
    size_t pos = input.find(' ');
    if (pos == std::string::npos) throw std::invalid_argument("No space found.");

    std::string s = input.substr(0, pos);
    std::string r = input.substr(pos + 1);

    if (suits.find(s) == suits.end())
        throw std::invalid_argument("Invalid suit.");
    if (ranks.find(r) == ranks.end())
        throw std::invalid_argument("Invalid rank.");

    return Card{ suits[s], ranks[r] };
}

int main() {
    while (true) {
        std::vector<Card> cards;
        std::cout << "Please enter 4 playing cards (e.g., Spade Queen):\n";
        for (int i = 1; i <= 4; ++i) {
            while (true) {
                std::cout << "Card " << i << ": ";
                std::string input;
                std::getline(std::cin, input);
                try {
                    cards.push_back(parseCard(input));
                    break;
                }
                catch (const std::exception& e) {
                    std::cout << "Error: " << e.what() << " Please try again (Format: Suit Rank).\n";
                }
            }
        }

        quickSort(cards, 0, cards.size() - 1);

        std::cout << "\nSorted cards (from highest to lowest):\n";
        for (const auto& c : cards)
            std::cout << toString(c) << '\n';

        std::string again;
        std::cout << "\nDo you want to play again? (yes/no): ";
        std::getline(std::cin, again);
        if (again != "yes" && again != "Yes") {
            std::cout << "Thank you for playing with us.\n";
            std::this_thread::sleep_for(std::chrono::seconds(10));
            break;
        }
        std::cout << "\nNew game begins...\n\n";
    }
    return 0;
}