Sorting algorithms (asm x86)
There are many different sorting algorithms. They all have their own pros and cons, so the “perfect algorithm” depends on the needs of the user.
As an exercise for myself and a way to practice my knowledge of sorting algorithms, I decided to create asm x86 versions of 3 different algorithms: quicksort, insertion sort and gnome sort.
As a test, I also made C++ versions of these algorithms and tested their speeds, to compare and see if my manually created assembly code managed to match the speed or maybe even improve on the one created by the compiled C++.
Now, onto the algorithms.
Gnome Sort
The slowest but simplest algorithm in this list. This exchanging algorithm is a bit of a combination between insertion sort and bubble sort.
As mentioned, it’s not very fast, but the size of the code is tiny compared to the other algorithms.
The gnome sort is a good introduction to sorting algorithms, but in practice it’s better to use a faster, more efficient algorithm instead.
It has an average and worst case running time of O(n^2).
Pros: Tiny code size. Very easy to understand.
Cons: Pretty slow compared to the other algorithms.
Go to Gnome Sort…
Insertion Sort
As the name says, this algorithm uses an insertion method (as opposed to the Gnome Sort’s exchange method) in order to sort the list.
It’s faster than Gnome Sort, and the code is not that much bigger. It has an average and worst case running time of O(n^2).
Pros: Good for small lists.
Cons: Not very efficient on large lists.
Go to Insertion Sort…
Quicksort
The fastest algorithm of the 3. Uses a “divide and conquer” method, this means, it partitions the list recursively and sorts it by using a pivot value.
It has a very good average case of O(n log n), but it’s worst case is still O(n^2).
Pros: Very fast.
Cons: Unstable.
Go to Quicksort…
Comparison
The algorithms were tested by sorting 100 lists of 10,000 random integers.
They were also compared with C++ versions of the algorithms and they all managed to have around the same speed, with exception of the insertion sort, which ended up being slower than the C++ version.
Here are the average times, in seconds, that it took each algorithm to sort 10,000 random integers, in order from fastest to slowest:
Quicksort 0.0007905865 seconds
Insertion 0.07452373 seconds
Gnome 0.1484936 seconds