Bubblewrap sort

The problem

Anyone familiar with computer science algorithms knows about bubble sort. In this algorithm, you sort a list of things in “bubbles” by going over it repeatedly in sequence and swapping two bubbles next to one another until they’re all sorted.

Although this algorithm is simple to explain, it’s really inefficient as you will have to go over the list potentially many, many times until it’s sorted.

And it has one more problem: isn’t the most fun part of bubbles popping them?

The solution: Bubblewrap sort

Enter bubblewrap sort! This takes advantage of a shortcut most sorting algorithms haven’t even thought of. Here’s how it works.

After putting everything in our list in bubbles, we simply pop all the bubbles. You know, like bubblewrap. Now the list is empty, and by definition an empty list is a sorted list.

C++ code listing

Here’s an implementation of bubblewrap sort on a C++ vector:

#include <vector>
#include <iostream>

// Perform a bubblewrap sort.
template <class T>
void bubblewrap_sort(std::vector<T>& vec) {
    vec.clear();
}

// Print the contents of a vector.
template <class T>
void print_vector(std::vector<T>& vec) {
    std::cout << "Vector:";
    for (T content : vec) {
        std::cout << ' ' << content;
    }
    std::cout << std::endl;
}

int main() {
    // Create an unsorted list of integers.
    std::vector<int> list_to_sort;
    list_to_sort.push_back(3);
    list_to_sort.push_back(6);
    list_to_sort.push_back(1);
    list_to_sort.push_back(-2);
    list_to_sort.push_back(10);

    // Print our original list.
    print_vector(list_to_sort);

    // Run bubblewrap sort and print our list again!
    bubblewrap_sort(list_to_sort);
    print_vector(list_to_sort);

    return 0;
}

Program output:

Vector: 3 6 1 -2 10
Vector:

Conclusion

Traditionally we expect a sorting algorithm to return a list with the same elements in a sorted order, but if we shave those requirements down to just returning a sorted list — any sorted list, really — the problem becomes much simpler to solve. And more fun, because there’s nothing more satisfying than popping bubblewrap.