img/home.png


      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.


  Animation example with random data

  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.

Comparison table:

AS - Artificial QuickSort with InsertionSort
QS - QuickSort with InsertionSort

  NumberOfRec = 30.000.000 NumberOfRec = 10.000.000 NumberOfRec = 1.000.000
Data = Rnd(-10000000, 10000000) AS = 12437 ms
QS = 12781 ms
AS = 3968 ms
QS = 4046 ms
AS = 343 ms
QS = 359 ms
Data = Rnd(-1000000, 1000000) AS = 10500 ms
QS = 11828 ms
AS = 3563 ms
QS = 3891 ms
AS = 344 ms
QS = 360 ms
Data = Rnd(-100000, 100000) AS =  8562 ms
QS = 10812 ms
AS = 2859 ms
QS = 3484 ms
AS = 313 ms
QS = 343 ms
Data = Rnd(-10000, 10000) AS =  6875 ms
QS = 10078 ms
AS = 2313 ms
QS = 3188 ms
AS = 219 ms
QS = 282 ms
Data = Rnd(-100, 100) AS =  3703 ms
QS =  8407 ms
AS = 1234 ms
QS = 2656 ms
AS = 125 ms
QS = 234 ms
Data = Rnd(-10, 10) AS =  2094 ms
QS =  7640 ms
AS =  703 ms
QS = 2453 ms
AS =  78 ms
QS = 203 ms
















Demonstration:

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.