Artificial QuickSort Updated: 10.04.2007 19:00 CET
Here we are. A new sorting algorithm has been invented, using the Critticall programming tool. It's worth to mention, since it's faster then QuickSort. In fact it degenerates to some kind of (fast!) QuickSort, when purely random arrays are to be sorted. For more frequent everyday arrays with some equal elements, it's significantly faster than the old champion.
You are free to test it and use it every way you wish, the code is bellow the gif algorithm demonstration.
Artificial QuickSort QuickSort
with InsertionSort with InsertionSort
Show ORTO Artificial QuickSort source C++ code
ORTO means strictly comparison version of the Artificial sort. A little slower but still faster than Quick sort
Use this algorithm every way you want. Especially for large arrays the difference may be substantial. Everything comes down to the fact, that the information that something is already sorted is used on one hand, and that the middle point between two unsorted elements is generally a good pivot - on the other.
As this algorithm somehow managed to escaped every human to spot it for the past forty years, it's quite conceivable, it's not the end of the story, yet. Stay tuned for further advances or try it for yourself, using Critticall.
The main innovation compared to the QuickSort is: Don't sort an already sorted segment!. A lot of repeating partitioning can be avoided, if the already ordered segments are just tested once and left alone - no additional tests, let alone additional partitioning. For the QuickSort, a sorted segment is a subject of maybe a lot of the repetitive comparing, partitioning and stacking. Artificial QuickSort can harness the order it encounters. What often gives it a considerable edge.
AS - Artificial QuickSort with InsertionSort
QS - QuickSort with InsertionSort
Every vertical line represents the array and every pixel is an element. Bigger (brighter) and smaller (darker) are randomly mixed on the left side and sorted on the right. The transition during the program's execution is clearly visible.
What has really happened that day, back in 2007, when the ArtificialQuickSort was born? We have just realized then, that the Several Unique Sort, which has evolved further to the Two Unique in the environment of exactly two different keys to sort, has a potential to partition a file into two parts. Those greater than the pivot and those not greater than the pivot. Whatever the pivot may be. So, we wrote the code. After some additional cooking inside Critticall, we basically got what is now the Artificial QuickSort.
One may ask, what is the difference between Quick and Artificial? The answer is - in the partitioning! Artificial partitions differently or not at all, unless it's absolutely necessary.