This test was performed with an array containing C++ strings. Each string had 50 characters, all of which had the same value except for the last 8 characters which were randomly generated (in a similar way as the integers in the first test).
Since the gcc std::string uses a copy-on-write mechanism, copying the strings is fast. This means that in this test comparing is slow and copying is fast.
The array of 1 million items was skipped because it was extremely slow to test.
Insertion sort makes large amounts of comparisons, which penalizes it in this test, even with just 100 items. The other algorithms don't show big surprises.
| Random | Almost sortd | Almost rev. | Random end | |||||
|---|---|---|---|---|---|---|---|---|
| Alg. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. |
| Insert. | 2567 | 2670 | 418 | 517 | 4704 | 4827 | 2567 | 2670 |
| Shell | 767 | 1076 | 463 | 747 | 731 | 1092 | 767 | 1076 |
| Heap | 1027 | 1743 | 1069 | 1882 | 957 | 1558 | 1027 | 1743 |
| Merge | 558 | 800 | 470 | 800 | 424 | 800 | 558 | 800 |
| Quick | 1061 | 475 | 2812 | 241 | 2055 | 335 | 1061 | 475 |
| Quick2 | 783 | 724 | 691 | 392 | 599 | 487 | 783 | 724 |
Shell sort seems to beat heap sort in this case. The vanilla quicksort shows pathological behaviour already (the "random end" test was already so much slower than everything else that it was skipped here).
| Random | Almost sortd | Almost rev. | Random end | |||||
|---|---|---|---|---|---|---|---|---|
| Alg. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. |
| Shell | 101337 | 136523 | 76288 | 109844 | 81538 | 118858 | 67958 | 101359 |
| Heap | 107693 | 171329 | 109581 | 177595 | 103763 | 161284 | 111988 | 181249 |
| Merge | 56824 | 70000 | 51726 | 70000 | 51444 | 70000 | 34611 | 70000 |
| Quick | 95199 | 42908 | 333520 | 22003 | 216123 | 31160 | 1031320 | 27129 |
| Quick2 | 74180 | 56380 | 81402 | 32047 | 81094 | 38124 | 130385 | 33534 |
At least the vanilla quicksort behaves consistently, unlike the
optimized one which, once again quite unexplicably, cannot handle the
last test properly. Curiously even std::sort shows signs
of difficulty with the last case.
| Random | Almost sortd | Almost rev. | Random end | |||||
|---|---|---|---|---|---|---|---|---|
| Alg. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. |
| Shell | 3880706 | 4877275 | 2891093 | 3851415 | 2922984 | 3950486 | 1643318 | 2599076 |
| Heap | 3019541 | 4724686 | 3014609 | 4775544 | 2937796 | 4518734 | 3132341 | 4973705 |
| Merge | 1566507 | 1800000 | 1464664 | 1800000 | 1463973 | 1800000 | 879307 | 1800000 |
| Quick | 2549390 | 1153934 | 9788949 | 582005 | 6086723 | 840932 | - | - |
| Quick2 | 2016139 | 1433387 | 2157357 | 776719 | 2214806 | 908138 | 33061360 | 554214 |
Shell sort shows its power over heap sort (albeit slightly). It might be safe to conclude that shell sort may be even a better choice than heap sort when comparison is slow.
Slow comparison seems to accentuate the difficult cases for quicksort.
Even std::sort started showing signs of problems handling
the difficult "random end" case.
Due to the low amount of comparisons performed by merge sort and its consistent amount of assignments, it performs very well in this case, where comparison is slow and assignment fast.