Martin Broadhurst

Sorting Algorithms

Preface

These are some sorting algorithms I've written in C++.

Contents

Bubble sort

bubble_sort.h

In a bubble sort, a series of passes is made over the data, and in each pass, every pair of adjacent elements is compared. If they are in the wrong order, they are swapped. The sort completes when no changes have been made in a pass. In each pass the maximum element is "bubbled" to the end, as it will be swapped with every succeeding element, and consequently becoming a part of the next comparison. The effect of this is that a sorted sublist is built up at the right of the input list. The end of the sublist to be sorted is shortened by one element after each pass to avoid examining the sorted sublist.

template <class RandomAccessIterator>
void bubble_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    bool finished = false;
    RandomAccessIterator it, end = last - 1;
    while (!finished) {
        bool changed = false;
        for (it = first; it < end; ++it) {
            if (*it > *(it + 1)) {
                std::swap(*it, *(it + 1));
                changed = true;
            }
        }
        if (changed) {
            --end;
        }
        else {
            finished = true;
        }
    }
}

Cocktail sort

cocktail_sort.h

By implementing a bubble sort bidirectionally, with the direction of each pass alternating, both the smallest and largest elements of the unsorted range are put in their proper place on each pass. This has the advantage of moving small elements at the end of the range to their proper place much more quickly. The effect is that a sorted sublist is built up at each end of the input list, and the sublist still to be sorted is correspondingly reduced by one element at each end after each pass.

template <class RandomAccessIterator>
void cocktail_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    bool finished = false;
    RandomAccessIterator it, begin = first, end = last - 1;
    while (!finished) {
        // Forward pass
        bool changed = false;
        for (it = begin; it < end; ++it) {
            if (*it > *(it + 1)) {
                std::swap(*it, *(it + 1));
                changed = true;
            }
        }
        if (changed) {
            --end;
        }
        else {
            finished = true;
        }
        if (!finished) {
            // Reverse pass
            changed = false;
            for (it = end; it > begin; --it) {
                if (*it < *(it - 1)) {
                    std::swap(*it, *(it - 1));
                    changed = true;
                }
            }
            if (changed) {
                ++begin;
            }
            else {
                finished = true;
            }
        }
    }
}

Tree Sort

tree_sort.h

A binary tree is a sorted data structure, and a list can be sorted by inserting its elements into a binary tree, and then retrieving them in order.

template <class RandomAccessIterator>
void tree_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    treenode<RandomAccessIterator>* tree = treenode<RandomAccessIterator>::build(first, last);
    tree->write(&first);
    tree->destroy();
}

This sort requires auxilliary storage, and perhaps in C++ it should have a different interface in order to allow an Allocator to be supplied by the client.

This is the process of building up the tree:

    static treenode<RandomAccessIterator>* build(RandomAccessIterator first, RandomAccessIterator last)
    {
        treenode<RandomAccessIterator>* root = NULL;
        for (RandomAccessIterator it = first; it < last; ++it) {
            treenode<RandomAccessIterator>* node = new treenode<RandomAccessIterator>(*it);
            if (root == NULL) {
                root = node;
            }
            else {
                treenode<RandomAccessIterator>* current = root,* previous = NULL;
                bool less;
                while (current != NULL) {
                    less = node->value_ < current->value_;
                    previous = current;
                    current = less ? current->left_ : current->right_;
                }
                if (less) {
                    previous->left_ = node;
                }
                else {
                    previous->right_ = node;
                }
            }
        }
        return root;
    }

Once the tree has been assembled, it is traversed in order using a recursive function and its contents are stored in the iterator. Note that the iterator is passed by address; this is how you ensure that a value is shared across all stack frames in a recursive algorithm.

    void write(RandomAccessIterator* it) const
    {
        if (left_) {
            left_->write(it);
        }
        **it = value_;
        ++(*it);
        if (right_) {
            right_->write(it);
        }
    }

After the sorted data has been stored back to the iterator, the tree is recursively destroyed. This needs to be performed in postorder so that the subtrees are destroyed before the parent node.

    void destroy()
    {
        if (left_) {
            left_->destroy();
        }
        if (right_) {
            right_->destroy();
        }
        delete this;
    }

Selection sort

selection_sort.h

In a selection sort the data is searched for the minimum (or maximum) element, and this is swapped with the element in its place at the end. As with a bubble sort, the end of the range to be sorted is adjusted after each pass as a sorted sublist is built up at the end. The construction of the sorted range is identical to that in a bubble sort, but it is performed much more efficiently because there are fewer swaps.

template <class RandomAccessIterator>
void selection_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    RandomAccessIterator begin = first;
    while (begin < last) {
        RandomAccessIterator it, min;
        bool started = false;
        for (it = begin; it < last; ++it) {
            if (!started || *it < *min) {
                min = it;
            }
            started = true;
        }
        std::swap(*min, *begin);
        ++begin;
    }
}

Min-max sort

minmax_sort.h

One can perform a selection sort and simultaneously search for the minimum and maximum element and move them to their proper places in each pass. This has the effect of building up a sorted sublist at each end, with the unsorted part becoming smaller from each ends, as in a cocktail sort. Again, the construction of the sorted ranges is performed much more efficiently in this sort than a cocktail sort because there are fewer swaps.

template <class RandomAccessIterator>
void minmax_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    RandomAccessIterator begin = first;
    RandomAccessIterator end = last - 1;
    while (begin < end) {
        RandomAccessIterator it, min, max;
        bool started = false;
        for (it = begin; it <= end; ++it) {
            if (!started) {
                min = it;
                max = it;
                started = true;
            }
            else {
                if (*it < *min) {
                    min = it;
                }
                else if (*it > *max) {
                    max = it;
                }
            }
        }
        if (max == begin && min == end) {
            // Swap min and max only
            std::swap(*max, *min);
        }
        else if (max == begin) {
            // Swap max and end first
            std::swap(*max, *end);
            std::swap(*min, *begin);
        }
        else {
            // Swap min and begin first
            std::swap(*min, *begin);
            std::swap(*max, *end);
        }
        ++begin;
        --end;
    }
}

Example program

Below is an example program to exercise the sorting algorithms:

#include <vector>
#include <iostream>
#include <functional>
#include <iterator>

#include "bubble_sort.h"
#include "cocktail_sort.h"
#include "tree_sort.h"
#include "selection_sort.h"
#include "minmax_sort.h"

namespace
{

template <class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last)
{
    typedef typename std::iterator_traits<ForwardIterator>::value_type T;
    return std::adjacent_find(first, last, std::greater<T>()) == last;
}

};

int main()
{
    typedef std::vector<int>::iterator I;
    typedef void (*sortfn)(I, I);
    sortfn sorts[] = { bubble_sort<I>, cocktail_sort<I>, tree_sort<I>, selection_sort<I>, minmax_sort<I> };
    const size_t numsorts = sizeof(sorts) / sizeof(sortfn);
    std::vector<int> numbers;
    for (unsigned int i = 0; i < 100; i++) {
        numbers.push_back(rand());
    }
    std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    for (unsigned int s = 0; s < numsorts; s++) {
        std::vector<int> vec(numbers.begin(), numbers.end());
        sorts[s](vec.begin(), vec.end());
        std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout << is_sorted(vec.begin(), vec.end()) << std::endl;
    }

    return 0;
}

Copyright (C) 2010 Martin Broadhurst