NO

Author Topic: mkqsort  (Read 4851 times)

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2091
mkqsort
« 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?
« Last Edit: February 29, 2016, 09:16:10 AM by TimoVJL »
May the source be with you

Snowman

  • Guest
Re: mkqsort
« Reply #1 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.

Maybe also take a look at Burstsort which, according to Wikipedia, delegates to multikey quicksort (so you don't have to start from scratch).

Offline jj2007

  • Member
  • *
  • Posts: 536
Re: mkqsort
« Reply #2 on: February 28, 2016, 08:02:26 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?

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2091
Re: mkqsort
« Reply #3 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 in this zip

Links:
Article here and some tests here
« Last Edit: February 29, 2016, 11:00:42 AM by TimoVJL »
May the source be with you

Grincheux

  • Guest
Re: mkqsort
« Reply #4 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!

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2091
Re: mkqsort
« Reply #5 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.
« Last Edit: March 03, 2016, 11:08:05 AM by TimoVJL »
May the source be with you

Offline jj2007

  • Member
  • *
  • Posts: 536
Re: mkqsort
« Reply #6 on: March 02, 2016, 07:57:52 PM »
Actually, that is pretty fast. I erroneously thought you meant sorting the bible line by line.

Grincheux

  • Guest
Re: mkqsort
« Reply #7 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 ?

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2091
Re: mkqsort
« Reply #8 on: March 05, 2016, 08:03:00 AM »
Not mine.
mkqsort is from here, 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
« Last Edit: March 06, 2016, 03:11:42 PM by TimoVJL »
May the source be with you