I test sort string pointers with qsort:
Strings from bible.txt.
mkqsort: 106ms
quicksort_str: 193ms
timsort: 235ms
PellesC qsort: 257ms
msvcrt.dll qsort: 346ms
BTW:
What is best algo for sorting string pointers?
I don't know what the best algorithm is. However I remember reading somewhere that std::sort() from the C++ standard library is based on Timsort (https://en.wikipedia.org/wiki/Timsort).
Maybe also take a look at Burstsort (https://en.wikipedia.org/wiki/Burstsort) which, according to Wikipedia, delegates to multikey quicksort (so you don't have to start from scratch).
Quote from: TimoVJL on February 24, 2016, 02:46:57 PM
I test sort string pointers with qsort:
Strings from bible.txt.
mkqsort: 106ms
quicksort_str: 193ms
timsort: 235ms
PellesC qsort: 257ms
msvcrt.dll qsort: 346ms
Looks a bit slow. Which cpu? Reading the file included? bible.txt around 4MB, 30,000 lines?
AMD 2.8 GHz.
Possible same bible.txt, not included here, but can be found from here (http://corpus.canterbury.ac.nz/descriptions/) in this (http://corpus.canterbury.ac.nz/resources/large.zip) zip
Links:
Article here (http://www.codeproject.com/Articles/1023591/Cplusplus-Implementations-of-Quicksort-Methods-for) and some tests here (http://www.codeproject.com/KB/recipes/1023591/words_from_tex_vc15_small.png)
Are there the same results with differents compilers?
Perhaphs the algorythm is not very fast but the compiler very good!
With msvc 2015 (19.00) and with -Ox 90 ms lowest value.
EDIT:
Results with random words:
268 ms MSVC 2015
271 ms gcc 4.6.1
279 ms gcc 5.1.0
288 ms PellesC
another word set 10 times AVG:
242 ms msvc 2015
248 ms gcc 3.4.5
260 ms gcc 4.8.1
264 ms gcc 5.1.0
265 ms PellesC 8
TestSort.zip PellesC project
TestSortMS.zip MSVC 19.00 compiled TestSortMS.exe.
test_words.zip test_words.exe for generating tests words.
Actually, that is pretty fast. I erroneously thought you meant sorting the bible line by line.
There are programmers like Timo that write very good algorythms, but I want to ask if Pelle can introduce them in the C library ?
Not mine.
mkqsort is from here (https://panthema.net/2013/parallel-string-sorting/parallel-string-sorting-0.6.5/src/sinha-copy-burstsort/C-burstsort.c.html), Timo Bingmann
New test set:
237 ms msvc 2015
265 ms PellesC 8
270 ms gcc 5.1.0
279 ms gcc 3.4.5
239 ms msvc 2015 x64
240 ms gcc 5.1.0 x64
256 ms PellesC 8 x64