Sorting Algorithms

During the development of my Sketch Processing application I reached a stage where the processing of each stroke was starting to take amounts of time noticable to the naked eye. At this point As the application was at an early stage of its life, my concerns were that if I was getting slowdown already then I had much worse to come.

Generally the processing was taking around seemingly exponential lengths of time in comparison to the number of points in the input.

After a quick time profiling addition to the code I was able to break down the processing in order to find if there was one chunk of code eating up my processing time. It soon became apparent that sorting the curvature and speed data (float arrays equal in size to the number of input points) was accounting for around 98.5% of the processing for an input of 200 points (around 2 seconds to process!).

I was relieved to find it was just a sorting algorithm that was the nuisance as I knew plenty about them and knew there would be a quicker solution available.

After reading through my basic and frankly terrible original sorting process, I realised that I'd written a type of Insertion Sort algorithm(one of the slower types of sort).

Some quick googling revealed a nice selection of algorithms and explained how there were basically 2 groups of comparison sorts. Fast, and slow.

These handy graphs show the variations in speed between the two groups, O(n^2) and O(n log n).





You can see that the slow algorithm graph has a vertical scale measured in hudreds of secionds whereas the fast algorithm graph has a vertical scale measured in tenths of seconds. This is clearly a huge difference.

Some more research helped me identify the Comb Sort as a reasonable solution. It acts in a similar way to the Bubble Sort, a relatively slow algorithm, however instead of comparing adjacent values, an initial gap of the data length is used and reduced by 1/(~1.3) each recursion over the data. This "combs" through the data and eliminates the comparison of a large portion of the unneccessary comparison, making the algorithm nearly as fast as a Quick Sort, whilst retaining the simplicity of a Bubble Sort.

Once the Comb Sort was applied, I recorded increases in speed of around 100 times, bringing the total processing time back down to unnoticable speeds.