Sorting algorithms for ya

03052018, 03:46 AM
This post was last modified: 03072018, 08:54 PM by codeguy. Edited 0 times
HashListSort: a new algorithm for rearranging stuff into order, quickly, invented by CodeGuy. Times of 11ms for N=1,000,000 have been bragged about on Quora. I assume as much on similar machines to mine (2.16 GHz), 4GB main, Intel Celeron mobile processor. Mine has them beaten by a factor of 2 AND this is ALSO faster than FlashSort() by a factor of 25% for large N (ie: N>=16777216). No more than N+25%N auxiliary memory as part of the HashTable is necessary. FAST? YouBetcha. Typical Performance is about 8,000,00Recs/GHzS for N=1,000,000. I doubt there's anything faster. It even includes a modified CountingSort() for HIGHLY redundant data. ALL of these methods are from my Sorting Library, modified for datatype to suit the DOUBLEprecision data used for this demo. To adapt for strings, you'll need to use _CVx functions part of qb64. I spent WEEKS testing this code after developing the prototype in FAR less. BTW, performance is very close to O(n). Only CountingSort will get you there faster. Even for N=100,000,000, execution time is 5.625s @ 2.16Ghz, roughly expected linear time compared to N=1,000,000 (7/128)s (.0546875s). 100 times as much data takes a VERY slight bit longer than the 1% version extrapolated to 100N. .15625s difference for time at N=1,000,000 done 100 times versus N=100,000,000, so (1/640)s difference at 100 times the data. for verification, I added the same sequence check used in ALL my testing. This actually takes LONGER than the sort itself. It is designed to stop and exit if an error is found, the way I know the result is correct if the results are displayed. Yes, it has been thoroughly tested for descending order too, JUST in case you wondered about that.
Code: TYPE MinMaxRec The EXACT same code as contributed to QB64.org  STEAL freely. Maybe even give props to CodeGuy for his contribution to fast and correct algorithms.
03052018, 04:16 AM
hi CodeGuy
I am wondering ..because you are good at invention Sorting algo can be used as sorting operators with precedence is there a such a algorythm? or i just babeling
basicPro forum:
http://basicpro.mipropia.com/smf/index.php EU Radioboard forum: http://euradioboard.createmybb3.com/index.php AurelSoft main site: http://aurelsoft.ucoz.com
03052018, 06:40 PM
This post was last modified: 03282018, 04:56 PM by eoredson. Edited 0 times
Hi, codeguy, I tested your HashListSort with NTest& = 2147483646 (signed long)
and got nothing: no memory error or anything. Erik. because in the qb64 wiki it states the upper range of an array element.
dndbbs project:
Links to my MUD: (strictly 16bit); AKA XP: Dndbbs executables http://www.filegate.net/pdn/pdnbasic/dnd50a1e.zip Dndbbs source http://www.filegate.net/pdn/pdnbasic/dnd50a1s.zip Dndbbs upgrade http://www.filegate.net/pdn/pdnbasic/dnd50a1u.zip DNDDOOR  https://bit.ly/EriksDNDDoor DUNGEON  https://bit.ly/EriksDungeon Interpreter  https://bit.ly/EriksSICK Hex Editor  https://bit.ly/EriksHexEditor Utilities  https://bit.ly/EriksUtils QB45 files:  https://bit.ly/EriksQB45 QB64shell  https://bit.ly/QB64shell Some old QB64 versions:  https://bit.ly/OldQB64
03072018, 02:14 PM
Unless you have sufficient RAM to store Array(), HashTable(), Count() and such, there is no way you'll be able to store nearly that many elements. That's 1220 GB alone for 2Billion+ elements with only 2GB main. Even on my machine, I couldn't do that. I would use either space on a drive or sort and merge in manageable chunks. This is a proofofconcept, which is proven to work within computing environment limits. I sincerely doubt you'll find ANY method faster for n>(1/2) billion. Even FlashSort(), the previous champion was 27+ times SLOWER than HashListSort(). Use it how it's designed and know its limits and it should serve you and others well. I don't know about you, but throughput of 10M+/GhzS is WAY beyond acceptable to me.
Aurel, It is entirely possible to use character orders not corresponding to ASCII. You would simply create your own table of character maps to sorting precedence. But this would require using custom comparators based on this mapping. If you wanted, you could make "z" sort before "b", but "a" sort before "b", although I haven't a clue about why anyone would want to do this.
03072018, 02:29 PM
This post was last modified: 03282018, 04:56 PM by eoredson. Edited 0 times
Which is why HashListSort() won't sort code:
Code: NTest& = 2147483646 Erik.
dndbbs project:
Links to my MUD: (strictly 16bit); AKA XP: Dndbbs executables http://www.filegate.net/pdn/pdnbasic/dnd50a1e.zip Dndbbs source http://www.filegate.net/pdn/pdnbasic/dnd50a1s.zip Dndbbs upgrade http://www.filegate.net/pdn/pdnbasic/dnd50a1u.zip DNDDOOR  https://bit.ly/EriksDNDDoor DUNGEON  https://bit.ly/EriksDungeon Interpreter  https://bit.ly/EriksSICK Hex Editor  https://bit.ly/EriksHexEditor Utilities  https://bit.ly/EriksUtils QB45 files:  https://bit.ly/EriksQB45 QB64shell  https://bit.ly/QB64shell Some old QB64 versions:  https://bit.ly/OldQB64
03072018, 03:46 PM
This post was last modified: 03072018, 03:49 PM by codeguy. Edited 0 times
Use it within reasonable limits and compare against FlashSort(), the previous sorting champ I dethroned and you'll see how much faster HashListSort (throughput around 10M+/GHzS) than FlashSort(). DWYT, already been there, done that and it was almost 28 times slower on the exact same dataset. (5.4s vs 160s+) not even a contest. Yes, you CAN eliminate the Sequence checking code. The sorting algorithm HashListSort() is CORRECT when used within its limits and used correctly.
03262018, 09:13 AM
This post was last modified: 03262018, 09:14 AM by codeguy. Edited 0 times
The newest iteration of CodeGuySortLib is at QB64(net) and QB64(org)
http://qb64.org/basbin/4041.txt, including a BFPRT implementation.
03282018, 02:55 PM
Quote:hi CodeGuy @Aurel: You are just babeling.. Erik. (all hail the great babel)
dndbbs project:
Links to my MUD: (strictly 16bit); AKA XP: Dndbbs executables http://www.filegate.net/pdn/pdnbasic/dnd50a1e.zip Dndbbs source http://www.filegate.net/pdn/pdnbasic/dnd50a1s.zip Dndbbs upgrade http://www.filegate.net/pdn/pdnbasic/dnd50a1u.zip DNDDOOR  https://bit.ly/EriksDNDDoor DUNGEON  https://bit.ly/EriksDungeon Interpreter  https://bit.ly/EriksSICK Hex Editor  https://bit.ly/EriksHexEditor Utilities  https://bit.ly/EriksUtils QB45 files:  https://bit.ly/EriksQB45 QB64shell  https://bit.ly/QB64shell Some old QB64 versions:  https://bit.ly/OldQB64 
« Next Oldest  Next Newest »
