Pelles C forum

C language => Tips & tricks => Topic started by: TimoVJL on February 24, 2016, 02:46:57 PM

Title: mkqsort
Post by: 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

BTW:
What is best algo for sorting string pointers?

Title: Re: mkqsort
Post by: Snowman on February 26, 2016, 04:22:23 PM

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).

Title: Re: mkqsort
Post by: jj2007 on February 28, 2016, 08:02:26 PM

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?

Title: Re: mkqsort
Post by: TimoVJL on February 29, 2016, 08:21:10 AM

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)

Title: Re: mkqsort
Post by: Grincheux on February 29, 2016, 03:33:36 PM

Are there the same results with differents compilers?
Perhaphs the algorythm is not very fast but the compiler very good!

Title: Re: mkqsort
Post by: TimoVJL on February 29, 2016, 09:11:09 PM

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.

Title: Re: mkqsort
Post by: jj2007 on March 02, 2016, 07:57:52 PM

Actually, that is pretty fast. I erroneously thought you meant sorting the bible line by line.

Title: Re: mkqsort
Post by: Grincheux on March 05, 2016, 04:50:39 AM

There are programmers like Timo that write very good algorythms, but I want to ask if Pelle can introduce them in the C library ?

Title: Re: mkqsort
Post by: TimoVJL on March 05, 2016, 08:03:00 AM

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