I present a sorting algorithm I believe is quite unlike any you have seen before. Also one you will probably hope to never see again.

Most sorting algorithms are concerned with optimising the sorting of a list, to be either as fast as possible or using as little space as possible. To this end they employ cunning logic and are compared using various complexity, resource and efficiency metrics.

The approach I'm demonstrating here is intended as an example of an alternative. It's "pessimised" rather than "optimised" to demonstrate just how badly sorting can be done. So without further ado, here's the core class (in Java):

package never_use_me;

import java.util.List;
import java.util.Random;

public class randsort {

    /* create a static RNG to prevent reseeding skewing the randomness */
    private static Random rnd = new Random(System.currentTimeMillis());

    /**
    The only public method for this class. Takes a list of objects, returns
    them sorted by increasing hashCode. The sort algorithm is as follows:
    <ol>
    <li>if the list isn't sorted</li>
    <li>pick a random two elements in the list</li>
    <li>swap them</li>
    <li>repeat</li>
    </ol>

    Since this "pure" random sort takes far longer than I'm prepared to wait,
    this is now optimised to only swap the elements if the first is bigger
    than the second. This massively reduces the time taken to sort the list
    and sometimes has time almost comparable with selection sort.

    <b>Note that this is a completely mad sorting algorithm</b>, implemented 
    purely for amusement, don't even think about using this for real,
    unless you're feeling really lucky.
    */
    public void sort(List list) {
        // using optimisedSwap we can do a load of swaps between tests since
        // we know the list won't get unsorted by unnecessary swapping.
        while (!sorted(list)) {
            for (int i=0; i<5; i++) {
                optimisedSwap(
                    list, 
                    Math.abs(rnd.nextInt())%list.size(), 
                    Math.abs(rnd.nextInt())%list.size()
                );
            }
        }
    }

    private void swap(List list, int a, int b) {
        Object tmp = list.get(a);
        list.set(a,list.get(b));
        list.set(b,tmp);
    }

    private void optimisedSwap(List list, int a, int b) {
        int low = Math.min(a,b);
        int high = Math.max(a,b);
        if (list.get(low).hashCode() > list.get(high).hashCode()) {
            swap(list, low, high);
        }
    }

    /* 
    Check if the list is sorted. This checks every element is bigger than the 
    previous one in the list, by comparing the hashCode() of both elements.
    Could be optimised by caching hashCodes, as if we cared about speed!
    */
    private boolean sorted(List list) {
        for (int i=1; i<list.size();i++) {
            if (list.get(i-1).hashCode() > list.get(i).hashCode()) {
                return false;
            }
        }
        return true;
    }
}

I did originally do some tests with this against various sized arrays, both random and pre-sorted, to see what would happen. The outcomes were unsurprisingly terrible. If I can be bothered I may run some more tests for another blog post.

Previous Post Next Post