C++ sorting algorithm practice

sorts.cc

// Copyright (C) 2011 Dmitri Nikulin.
// All rights reserved.

#include <cassert>

#include <algorithm>
#include <iostream>
#include <vector>

template<class T>
void print(std::vector<T> const & xs) {
    for (size_t i = 0; i < xs.size(); i++)
        std::cout << xs.at(i) << " ";
    std::cout << std::endl;
}

struct Insertion {
    template<class T>
    static void sort(std::vector<T> & xs) {
        int const len = xs.size();
        // For each xs(i)...
        for (int i = 1; i < len; i++) {
            // Swap xs(i) into the correct position within xs(0..i).
            for (int j = i; j > 0; j--) {
                T & t1 = xs.at(j - 1);
                T & t2 = xs.at(j    );

                if (t1 > t2)
                    std::swap(t1, t2);
                else
                    break;
            }
        }
    }
};

struct Selection {
    template<class T>
    static void sort(std::vector<T> & xs) {
        int const len = xs.size();
        // For each xs(i)...
        for (int i = 0; i < len; i++) {
            int min = i;

            // Find the minimum of xs(i+1..n).
            for (int j = i + 1; j < len; j++) {
                T & t1 = xs.at(min);
                T & t2 = xs.at(j  );

                if (xs.at(min) > xs.at(j))
                    min = j;
            }

            // Swap xs(i) with the minimum.
            if (i != min)
                std::swap(xs.at(i), xs.at(min));
        }
    }
};

struct Heap {
    template<class T>
    static void sort(std::vector<T> & xs) {
        int const len = xs.size();

        // The array is entirely unsorted.

        for (int cut = 1; cut < len; cut++) {
            // The heap has absorbed one more element.
            // Heapify-up to restore heap properties.
            int at = cut;

            while (at > 0) {
                int const parent = ((at - 1) / 2);
                assert(parent >= 0);

                T & ia = xs.at(at);
                T & ip = xs.at(parent);

                if (ia > ip) {
                    // Swap-up to restore properties at this level.
                    std::swap(ia, ip);
                    at = parent;
                } else {
                    // No more swaps necessary for this element.
                    break;
                }
            }
        }

        // The array is a valid heap but not in linear order.

        for (int cut = len - 1; cut > 0; cut--) {
            // Swap the root element (max) of the heap with the last element.
            std::swap(xs.at(0), xs.at(cut));

            // The heap may be invalid.
            // Heapify-down to restore heap properties.
            int at = 0;

            while ((at * 2) < cut) {
                int const c1 = ((at * 2) + 1);
                int const c2 = ((at * 2) + 2);

                int c = c2;

                if ((c2 >= cut) || (xs.at(c1) > xs.at(c2)))
                    c = c1;

                if ((c < cut) && (xs.at(at) < xs.at(c))) {
                    std::swap(xs.at(at), xs.at(c));
                    at = c;
                } else {
                    // No more swaps necessary for this element.
                    break;
                }
            }
        }

        // The array is now sorted.
    }
};

struct Quick {
    template<class T>
    static void sort(std::vector<T> & xs, int min, int max) {
        // Exit for sub-arrays of size 0 and 1.
        if ((max - min) < 2)
            return;

        // Select a pivot from the middle of the sub-array.
        int const mid = (min + ((max - min) / 2));
        T   const med = xs.at(mid);

        // Swap pivot to the end.
        std::swap(xs.at(mid), xs.at(max - 1));

        // Partition around the pivot.
        int store = min;
        for (int i = min; i < (max - 1); i++) {
            if (xs.at(i) < med)
                std::swap(xs.at(i), xs.at(store++));
        }

        // Move the pivot to its final place.
        std::swap(xs.at(store), xs.at(max - 1));

        // Sort elements less than the pivot.
        sort(xs, min, store);

        // Store elements greater than or equal to the pivot.
        // This call is a tail-call.
        sort(xs, store + 1, max);
    }

    template<class T>
    static void sort(std::vector<T> & xs) {
        sort(xs, 0, xs.size());
    }
};

struct Merge {
    template<class T>
    static void sort(std::vector<T> & xs, int min, int max) {
        int const len = (max - min);

        // Exit for sub-arrays of size 0 and 1.
        if (len < 2)
            return;

        // Calculate middle position.
        int const mid = (min + (len / 2));

        // Recurse into sub-arrays.
        sort(xs, min, mid);
        sort(xs, mid, max);

        // Allocate merge buffer.
        std::vector<T> ms(len);

        // Iteratively select minimum element.
        int i1 = min, i2 = mid, i = 0;
        while ((i1 < mid) && (i2 < max)) {
            T const & x1 = xs.at(i1);
            T const & x2 = xs.at(i2);

            if (x1 <= x2) {
                ms.at(i) = x1;
                i1++;
            } else {
                ms.at(i) = x2;
                i2++;
            }

            i++;
        }

        // Finish elements from lower half.
        while (i1 < mid)
            ms.at(i++) = xs.at(i1++);

        // Finish elements from upper half.
        while (i2 < max)
            ms.at(i++) = xs.at(i2++);

        // Return elements to original array.
        for (int i = 0; i < len; i++)
            xs.at(min + i) = ms.at(i);
    }

    template<class T>
    static void sort(std::vector<T> & xs) {
        sort(xs, 0, xs.size());
    }
};

template<class T>
void testSTL(std::vector<T> const & xs) {
    std::vector<T> xs1(xs);
    std::sort(xs1.begin(), xs1.end());
    print<T>(xs1);
}

template<class T, class S>
void testOne(std::vector<T> const & xs) {
    std::vector<T> xs1(xs);
    S::sort(xs1);
    print<T>(xs1);
}

template<class T>
void test(std::vector<T> const & xs) {
    std::cout << "STL:" << std::endl;
    testSTL<T>(xs);
    std::cout << std::endl;

    std::cout << "Insertion:" << std::endl;
    testOne<T, Insertion>(xs);
    std::cout << std::endl;

    std::cout << "Selection:" << std::endl;
    testOne<T, Selection>(xs);
    std::cout << std::endl;

    std::cout << "Heap:" << std::endl;
    testOne<T, Heap>(xs);
    std::cout << std::endl;

    std::cout << "Quick:" << std::endl;
    testOne<T, Quick>(xs);
    std::cout << std::endl;

    std::cout << "Merge:" << std::endl;
    testOne<T, Merge>(xs);
    std::cout << std::endl;
}

void test0() {
    std::vector<int> xs;
    test(xs);
}

void test1() {
    std::vector<int> xs;
    xs.push_back(7);
    test(xs);
}

void test7() {
    std::vector<int> xs;
    xs.push_back(7);
    xs.push_back(2);
    xs.push_back(3);
    xs.push_back(1);
    xs.push_back(9);
    xs.push_back(-2);
    xs.push_back(0);
    test(xs);
}

int main(int argc, char **argv) {
    test0();
    test1();
    test7();
    return 0;
}