Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: Dimster on November 03, 2019, 11:25:30 am

Title: Top 10 Algorythm
Post by: Dimster on November 03, 2019, 11:25:30 am
I have a very simple routine coded to get top 3 scores and names. It opens and closes the same data file multiple times. Pretty simple routine but as the data file gets larger its taking a little more time to display the results. Not that worried about it but was looking for suggestions on improving the coding. Here is a mainstay of the routine.
Code: QB64: [Select]
  1. 'SORTING FOR THE TOP 3 (INCLUDING TIES)
  2.  
  3. ' Assume a sequential data file with Name$ and Score
  4. ' Assume the file has been open as file #1
  6.     INPUT #1, Name$, Score
  7.     IF Score > HighScore1 AND Name$ <> HighName1$ THEN
  8.         HighScore1 = Score
  9.         HighName1$ = Name$
  10.     END IF
  13. 'open
  15.     INPUT #1, Name$, Score
  16.     IF Score > HighScore2 AND Score < HighScore1 THEN
  17.         HighScore2 = Score
  18.         HighName2$ = Name$
  19.     END IF
  22. 'open
  23.  
  25.     INPUT #1, Name$, Score
  26.     IF Score > HighScore3 AND Score < HighScore1 AND Score < HighScore2 THEN
  27.         HighScore3 = Score
  28.         HighName3$ = Name$
  29.     END IF
  32. 'open
  33.  
  35.     INPUT #1, Name$, Score
  36.     IF Score = HighScore1 AND Name$ <> HighName1$ THEN
  37.         HighScore2 = Score
  38.         HighName2$ = Name$
  39.     END IF
  40.     IF Score = HighScore2 AND Name$ <> HighName2$ THEN
  41.         HighScore3 = Score
  42.         HighName3$ = Name$
  43.     END IF
  44.  
Title: Re: Top 10 Algorythm
Post by: SMcNeill on November 03, 2019, 11:43:04 am
Wouldn’t the easiest way just be to open the file once, read the information into an array, and then toss it into a simple sorting routine?
Title: Re: Top 10 Algorythm
Post by: Petr on November 03, 2019, 01:11:21 pm
I also tried to write something on this topic:

Code: QB64: [Select]
  1. 'add and sort name and score to txt file: (based on principle, that score is not negative value)
  2.  
  3. file$ = "Score.txt"
  4. nfile$ = "Score2.txt"
  5. TYPE Score
  6.     N AS STRING
  7.     S AS INTEGER
  9. REDIM S(0) AS Score
  10.  
  11. INPUT "Insert name (string), score (number)"; n$, nr
  13. OPEN "i", ch, file$
  14.  
  16.     INPUT #ch, S(row).N, S(row).S
  17.     row = row + 1
  18.     REDIM _PRESERVE S(row) AS Score
  20. S(row).N = n$: S(row).S = nr 'in last position in array are new values from input
  22.  
  23. PRINT "Previous order:"
  24. FOR t = LBOUND(S) TO UBOUND(S)
  25.     PRINT S(t).N, S(t).S
  27.  
  30. PRINT "New order:"
  31.  
  32. 'search first, maximal value, then write it to new array, set it in array to mimnimal value (-9999) and again search maximum value
  33. REDIM NOrd(row) AS Score 'NOrd = New Order array
  34.  
  35. FOR complet = 0 TO row
  36.     maximum = -9999
  37.     FOR t = LBOUND(S) TO UBOUND(S)
  38.         IF maximum < S(t).S THEN maximum = S(t).S: i = t
  39.     NEXT
  40.     'we have maximal value. Write it to new array NOrd:
  41.     NOrd(complet).N = S(i).N
  42.     NOrd(complet).S = S(i).S
  43.     S(i).S = -9999
  45.  
  46. FOR t = LBOUND(nord) TO UBOUND(nord)
  47.     PRINT NOrd(t).N, NOrd(t).S
  49.  
  50. 'write sorted values to new text file:
  51. OPEN "o", ch, nfile$
  52. FOR t = LBOUND(nord) TO UBOUND(nord)
  53.     PRINT #ch, NOrd(t).N, NOrd(t).S
  56.  
Title: Re: Top 10 Algorythm
Post by: TempodiBasic on November 03, 2019, 04:24:36 pm
Hi Dimster

about your goal here my way to get this
Code: QB64: [Select]
  1. ' Goal:
  2. REM  to get top 3 scores and names.
  3. REM It opens and closes the same data file multiple times.
  4. REM as the data file gets larger its taking a little more time to display the results.
  5.  
  6. ' Materials:
  7. REM a text file with in sequence a name of gamer and the score got
  8.  
  9. TYPE Reco
  10.     Gname AS STRING
  11.     Score AS INTEGER
  13.  
  14. DIM top3(0 TO 3) AS Reco
  15. SCREEN _NEWIMAGE(600, 480, 32)
  16. COLOR _RGBA32(0, 127, 127, 255), _RGBA32(0, 0, 0, 255)
  17. _PRINTSTRING (10, 20), "start reading file text"
  18.  
  19. OPEN "Score.txt" FOR INPUT AS #1
  21.     INPUT #1, top3(0).Gname, top3(0).Score
  22.     ' for output during elaboration of data file
  23.     _PRINTSTRING (200, 40), top3(0).Gname + " " + STR$(top3(0).Score)
  24.     _PRINTSTRING (200, 60), top3(1).Gname + " " + STR$(top3(1).Score)
  25.     _PRINTSTRING (200, 90), top3(2).Gname + " " + STR$(top3(2).Score)
  26.     _PRINTSTRING (200, 120), top3(3).Gname + " " + STR$(top3(3).Score)
  27.     _DELAY 1
  28.     CLS
  29.     ' end of verbose output ;-)
  30.     IF top3(0).Score > top3(1).Score THEN
  31.         top3(3).Score = top3(2).Score
  32.         top3(3).Gname = top3(2).Gname
  33.         top3(2).Score = top3(1).Score
  34.         top3(2).Gname = top3(1).Gname
  35.         top3(1).Score = top3(0).Score
  36.         top3(1).Gname = top3(0).Gname
  37.     ELSEIF top3(0).Score > top3(2).Score THEN
  38.         top3(3).Score = top3(2).Score
  39.         top3(3).Gname = top3(2).Gname
  40.         top3(2).Score = top3(0).Score
  41.         top3(2).Gname = top3(0).Gname
  42.     ELSEIF top3(0).Score > top3(3).Score THEN
  43.         top3(3).Score = top3(0).Score
  44.         top3(3).Gname = top3(0).Gname
  45.     END IF
  48. _PRINTSTRING (10, 40), " Name   Score"
  49. _PRINTSTRING (10, 60), top3(1).Gname + " " + STR$(top3(1).Score)
  50. _PRINTSTRING (10, 90), top3(2).Gname + " " + STR$(top3(2).Score)
  51. _PRINTSTRING (10, 120), top3(3).Gname + " " + STR$(top3(3).Score)
  52.  
  53.  

using UDT

  [ This attachment cannot be displayed inline in 'Print Page' view ]  

but it is not necessary, you can use also 2 parallel arrays like here


Code: QB64: [Select]
  1. ' Goal:
  2. REM  to get top 3 scores and names.
  3. REM It opens and closes the same data file multiple times.
  4. REM as the data file gets larger its taking a little more time to display the results.
  5.  
  6. ' Materials:
  7. REM a text file with in sequence a name of gamer and the score got
  8.  
  9. CONST One = 1, Two = 2, Three = 3, Zero = 0
  10. DIM top3(Zero TO Three) AS INTEGER, top3Name(Zero TO Three) AS STRING
  11. SCREEN _NEWIMAGE(600, 480, 32)
  12. COLOR _RGBA32(0, 127, 127, 255), _RGBA32(0, 0, 0, 255)
  13. _PRINTSTRING (10, 20), "start reading file text"
  14.  
  15. OPEN "Score.txt" FOR INPUT AS #1
  17.     INPUT #1, top3Name(Zero), top3(Zero)
  18.     ' for output during elaboration of data file
  19.     _PRINTSTRING (200, 40), top3Name(Zero) + " " + STR$(top3(Zero))
  20.     _PRINTSTRING (200, 60), top3Name(One) + " " + STR$(top3(One))
  21.     _PRINTSTRING (200, 90), top3Name(Two) + " " + STR$(top3(Two))
  22.     _PRINTSTRING (200, 120), top3Name(Three) + " " + STR$(top3(Three))
  23.     _DELAY 1
  24.     CLS
  25.     ' end of verbose output ;-)
  26.     IF top3(zero0) > top3(One) THEN
  27.         top3(Three) = top3(Two)
  28.         top3Name(Three) = top3Name(Two)
  29.         top3(Two) = top3(One)
  30.         top3Name(Two) = top3Name(One)
  31.         top3(One) = top3(Zero)
  32.         top3Name(One) = top3Name(Zero)
  33.     ELSEIF top3(Zero) > top3(Two) THEN
  34.         top3(Three) = top3(Two)
  35.         top3Name(Three) = top3Name(Two)
  36.         top3(Two) = top3(Zero)
  37.         top3Name(Two) = top3Name(Zero)
  38.     ELSEIF top3(Zero) > top3(Three) THEN
  39.         top3(Three) = top3(Zero)
  40.         top3Name(Three) = top3Name(Zero)
  41.     END IF
  44. _PRINTSTRING (10, 40), " Name   Score"
  45. _PRINTSTRING (10, 60), top3Name(One) + " " + STR$(top3(One))
  46. _PRINTSTRING (10, 90), top3Name(Two) + " " + STR$(top3(Two))
  47. _PRINTSTRING (10, 120), top3Name(Three) + " " + STR$(top3(Three))
  48.  
  49.  

so reading one time the file you can make top three in one shot!

Thanks Petr for Score.txt that I have used for my example.

IMHO the method showed by Petr let you read how many records you want and extract the three top .
IMHO excellent the method suggested by Steve that let you have a list in RAM to order for any parameter do you like to use. (also for this method do you need of UBOUND for adjourning the upper limit of the array for all data of the file.
Title: Re: Top 10 Algorythm
Post by: bplus on November 03, 2019, 07:33:43 pm
and my 2 cents from tool box, load and sort array at same time:
Code: QB64: [Select]
  1. _TITLE "Load and sort to array at same time" 'B+ 2019-10-26
  2. '2019-10-27 edited 2x with Steve's improvements thanks Steve!
  3. ' 2019-11-03 mod for name score data file
  4. TYPE dat
  5.     n AS STRING
  6.     s AS INTEGER
  8. DIM d(1 TO 100) AS dat 'dimensioned to something known to be > data lines
  9. OPEN "name_score.dat" FOR INPUT AS #1
  10. WHILE EOF(1) = 0
  11.     INPUT #1, N$, s
  12.     IF _TRIM$(N$) <> "" THEN
  13.         i = i + 1
  14.         PRINT N$, s
  15.         FOR j = 1 TO i - 1
  16.             IF s > d(j).s THEN
  17.                 FOR k = i TO j + 1 STEP -1
  18.                     d(k) = d(k - 1)
  19.                 NEXT
  20.                 EXIT FOR
  21.             END IF
  22.         NEXT
  23.         d(j).s = s: d(j).n = N$
  24.     END IF
  27. PRINT: PRINT " and sorted while loading array:"
  28. FOR j = 1 TO i
  29.     IF j < 4 THEN PRINT "Top"; j, d(j).n, d(j).s ELSE PRINT , d(j).n, d(j).s
  31.  
 [ This attachment cannot be displayed inline in 'Print Page' view ]  

EDIT: cut 4 lines
Title: Re: Top 10 Algorythm
Post by: Qwerkey on November 04, 2019, 04:38:10 am
I have nothing to add on sort routines.  But the correct spelling is "algorithm" - even you peculiar Americans spell it this way(?).  It is easy to confuse the spelling because of the word "rhythm" (a six-letter word with no vowels, although of course the y is acting as the vowel).
Title: Re: Top 10 Algorythm
Post by: SMcNeill on November 04, 2019, 06:09:39 am
Quote from: bplus on November 03, 2019, 07:33:43 pm
and my 2 cents from tool box, load and sort array at same time:
Code: QB64: [Select]
  1. _TITLE "Load and sort to array at same time" 'B+ 2019-10-26
  2. '2019-10-27 edited 2x with Steve's improvements thanks Steve!
  3. ' 2019-11-03 mod for name score data file
  4. TYPE dat
  5.     n AS STRING
  6.     s AS INTEGER
  8. DIM d(1 TO 100) AS dat 'dimensioned to something known to be > data lines
  9. OPEN "name_score.dat" FOR INPUT AS #1
  10. WHILE EOF(1) = 0
  11.     INPUT #1, N$, s
  12.     IF _TRIM$(N$) <> "" THEN
  13.         i = i + 1
  14.         PRINT N$, s
  15.         FOR j = 1 TO i - 1
  16.             IF s > d(j).s THEN
  17.                 FOR k = i TO j + 1 STEP -1
  18.                     d(k) = d(k - 1)
  19.                 NEXT
  20.                 EXIT FOR
  21.             END IF
  22.         NEXT
  23.         d(j).s = s: d(j).n = N$
  24.     END IF
  27. PRINT: PRINT " and sorted while loading array:"
  28. FOR j = 1 TO i
  29.     IF j < 4 THEN PRINT "Top"; j, d(j).n, d(j).s ELSE PRINT , d(j).n, d(j).s
  31.  

Here's the only reason why I don't usually advocate the "load and sort" method:

Code: QB64: [Select]
  1. CONST limit = 20000 'number of items to load and sort
  2.  
  3. DIM Array(limit) AS INTEGER
  4. DIM n(limit) AS INTEGER
  6. m = _MEM(Array())
  7. OPEN "temp.txt" FOR OUTPUT AS #1
  8. FOR i = 0 TO limit 'print a ton of entries
  9.     PRINT #1, RND * 10000
  12.  
  13.  
  14.  
  15.  
  16. OPEN "temp.txt" FOR INPUT AS #1
  17.  
  18. t## = TIMER
  19.  
  20. FOR i = 0 TO limit
  21.     INPUT #1, num
  22.     FOR j = 0 TO i - 1
  23.         IF num < n(j) THEN
  24.             FOR k = i TO j + 1 STEP -1
  25.                 n(k) = n(k - 1)
  26.             NEXT
  27.             EXIT FOR
  28.         END IF
  29.     NEXT
  30.     n(j) = num
  33. t1## = TIMER
  34.  
  35. PRINT USING "###.### seconds to load and sort together"; t1## - t##
  36.  
  37. t2## = TIMER
  38. OPEN "temp.txt" FOR INPUT AS #1
  39. FOR i = 0 TO limit
  40.     INPUT #1, Array(i)
  42. Sort m
  44. t3## = TIMER
  45. PRINT USING "###.### seconds to load and then sort"; t3## - t2##
  46.  
  47. FOR i = 0 TO limit STEP limit / 20 'and we'll print a selection of the data so we can compare results.
  48.     PRINT i, n(i), Array(i)
  49.     IF n(i) <> Array(i) THEN SLEEP
  51.  
  52.  
  53. SUB Sort (m AS _MEM)
  55.     $IF 64BIT THEN
  56.         DIM ES AS _INTEGER64, EC AS _INTEGER64
  57.     $ELSE
  58.         DIM ES AS LONG, EC AS LONG
  59.     $END IF
  60.  
  61.     IF NOT m.TYPE AND 65536 THEN EXIT SUB 'We won't work without an array
  62.     IF m.TYPE AND 1024 THEN DataType = 10
  63.     IF m.TYPE AND 1 THEN DataType = DataType + 1
  64.     IF m.TYPE AND 2 THEN DataType = DataType + 2
  65.     IF m.TYPE AND 4 THEN IF m.TYPE AND 128 THEN DataType = DataType + 4 ELSE DataType = 3
  66.     IF m.TYPE AND 8 THEN IF m.TYPE AND 128 THEN DataType = DataType + 8 ELSE DataType = 5
  67.     IF m.TYPE AND 32 THEN DataType = 6
  68.     IF m.TYPE AND 512 THEN DataType = 7
  69.  
  70.     'Convert our offset data over to something we can work with
  71.     DIM m1 AS _MEM: m1 = _MEMNEW(LEN(ES))
  72.     _MEMPUT m1, m1.OFFSET, m.ELEMENTSIZE: _MEMGET m1, m1.OFFSET, ES 'Element Size
  73.     _MEMPUT m1, m1.OFFSET, m.SIZE: _MEMGET m1, m1.OFFSET, EC 'Element Count will temporily hold the WHOLE array size
  74.     _MEMFREE m1
  75.  
  76.     EC = EC / ES - 1 'Now we take the whole element size / the size of the elements and get our actual element count.  We subtract 1 so our arrays start at 0 and not 1.
  77.     'And work with it!
  78.     DIM o AS _OFFSET, o1 AS _OFFSET, counter AS _UNSIGNED LONG
  79.  
  80.     SELECT CASE DataType
  81.         CASE 1 'BYTE
  82.             DIM temp1(-128 TO 127) AS _UNSIGNED LONG
  83.             DIM t1 AS _BYTE
  84.             i = 0
  85.             DO
  86.                 _MEMGET m, m.OFFSET + i, t1
  87.                 temp1(t1) = temp1(t1) + 1
  88.                 i = i + 1
  89.             LOOP UNTIL i > EC
  90.             i1 = -128
  91.             DO
  92.                 DO UNTIL temp1(i1) = 0
  93.                     _MEMPUT m, m.OFFSET + counter, i1 AS _BYTE
  94.                     counter = counter + 1
  95.                     temp1(i1) = temp1(i1) - 1
  96.                     IF counter > EC THEN EXIT SUB
  97.                 LOOP
  98.                 i1 = i1 + 1
  99.             LOOP UNTIL i1 > 127
  100.         CASE 2: 'INTEGER
  101.             DIM temp2(-32768 TO 32767) AS _UNSIGNED LONG
  102.             DIM t2 AS INTEGER
  103.             i = 0
  104.             DO
  105.                 _MEMGET m, m.OFFSET + i * 2, t2
  106.                 temp2(t2) = temp2(t2) + 1
  107.                 i = i + 1
  108.             LOOP UNTIL i > EC
  109.             i1 = -32768
  110.             DO
  111.                 DO UNTIL temp2(i1) = 0
  112.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS INTEGER
  113.                     counter = counter + 1
  114.                     temp2(i1) = temp2(i1) - 1
  115.                     IF counter > EC THEN EXIT SUB
  116.                 LOOP
  117.                 i1 = i1 + 1
  118.             LOOP UNTIL i1 > 32767
  119.         CASE 3 'SINGLE
  120.             DIM T3a AS SINGLE, T3b AS SINGLE
  121.             gap = EC
  122.             DO
  123.                 gap = 10 * gap \ 13
  124.                 IF gap < 1 THEN gap = 1
  125.                 i = 0
  126.                 swapped = 0
  127.                 DO
  128.                     o = m.OFFSET + i * 4
  129.                     o1 = m.OFFSET + (i + gap) * 4
  130.                     IF _MEMGET(m, o, SINGLE) > _MEMGET(m, o1, SINGLE) THEN
  131.                         _MEMGET m, o1, T3a
  132.                         _MEMGET m, o, T3b
  133.                         _MEMPUT m, o1, T3b
  134.                         _MEMPUT m, o, T3a
  135.                         swapped = -1
  136.                     END IF
  137.                     i = i + 1
  138.                 LOOP UNTIL i + gap > EC
  139.             LOOP UNTIL gap = 1 AND swapped = 0
  140.         CASE 4 'LONG
  141.             DIM T4a AS LONG, T4b AS LONG
  142.             gap = EC
  143.             DO
  144.                 gap = 10 * gap \ 13
  145.                 IF gap < 1 THEN gap = 1
  146.                 i = 0
  147.                 swapped = 0
  148.                 DO
  149.                     o = m.OFFSET + i * 4
  150.                     o1 = m.OFFSET + (i + gap) * 4
  151.                     IF _MEMGET(m, o, LONG) > _MEMGET(m, o1, LONG) THEN
  152.                         _MEMGET m, o1, T4a
  153.                         _MEMGET m, o, T4b
  154.                         _MEMPUT m, o1, T4b
  155.                         _MEMPUT m, o, T4a
  156.                         swapped = -1
  157.                     END IF
  158.                     i = i + 1
  159.                 LOOP UNTIL i + gap > EC
  160.             LOOP UNTIL gap = 1 AND swapped = 0
  161.         CASE 5 'DOUBLE
  162.             DIM T5a AS DOUBLE, T5b AS DOUBLE
  163.             gap = EC
  164.             DO
  165.                 gap = 10 * gap \ 13
  166.                 IF gap < 1 THEN gap = 1
  167.                 i = 0
  168.                 swapped = 0
  169.                 DO
  170.                     o = m.OFFSET + i * 8
  171.                     o1 = m.OFFSET + (i + gap) * 8
  172.                     IF _MEMGET(m, o, DOUBLE) > _MEMGET(m, o1, DOUBLE) THEN
  173.                         _MEMGET m, o1, T5a
  174.                         _MEMGET m, o, T5b
  175.                         _MEMPUT m, o1, T5b
  176.                         _MEMPUT m, o, T5a
  177.                         swapped = -1
  178.                     END IF
  179.                     i = i + 1
  180.                 LOOP UNTIL i + gap > EC
  181.             LOOP UNTIL gap = 1 AND swapped = 0
  182.         CASE 6 ' _FLOAT
  183.             DIM T6a AS _FLOAT, T6b AS _FLOAT
  184.             gap = EC
  185.             DO
  186.                 gap = 10 * gap \ 13
  187.                 IF gap < 1 THEN gap = 1
  188.                 i = 0
  189.                 swapped = 0
  190.                 DO
  191.                     o = m.OFFSET + i * 32
  192.                     o1 = m.OFFSET + (i + gap) * 32
  193.                     IF _MEMGET(m, o, _FLOAT) > _MEMGET(m, o1, _FLOAT) THEN
  194.                         _MEMGET m, o1, T6a
  195.                         _MEMGET m, o, T6b
  196.                         _MEMPUT m, o1, T6b
  197.                         _MEMPUT m, o, T6a
  198.                         swapped = -1
  199.                     END IF
  200.                     i = i + 1
  201.                 LOOP UNTIL i + gap > EC
  202.             LOOP UNTIL gap = 1 AND swapped = 0
  203.         CASE 7 'String
  204.             DIM T7a AS STRING, T7b AS STRING, T7c AS STRING
  205.             T7a = SPACE$(ES): T7b = SPACE$(ES): T7c = SPACE$(ES)
  206.             gap = EC
  207.             DO
  208.                 gap = INT(gap / 1.247330950103979)
  209.                 IF gap < 1 THEN gap = 1
  210.                 i = 0
  211.                 swapped = 0
  212.                 DO
  213.                     o = m.OFFSET + i * ES
  214.                     o1 = m.OFFSET + (i + gap) * ES
  215.                     _MEMGET m, o, T7a
  216.                     _MEMGET m, o1, T7b
  217.                     IF T7a > T7b THEN
  218.                         T7c = T7b
  219.                         _MEMPUT m, o1, T7a
  220.                         _MEMPUT m, o, T7c
  221.                         swapped = -1
  222.                     END IF
  223.                     i = i + 1
  224.                 LOOP UNTIL i + gap > EC
  225.             LOOP UNTIL gap = 1 AND swapped = false
  226.         CASE 8 '_INTEGER64
  227.             DIM T8a AS _INTEGER64, T8b AS _INTEGER64
  228.             gap = EC
  229.             DO
  230.                 gap = 10 * gap \ 13
  231.                 IF gap < 1 THEN gap = 1
  232.                 i = 0
  233.                 swapped = 0
  234.                 DO
  235.                     o = m.OFFSET + i * 8
  236.                     o1 = m.OFFSET + (i + gap) * 8
  237.                     IF _MEMGET(m, o, _INTEGER64) > _MEMGET(m, o1, _INTEGER64) THEN
  238.                         _MEMGET m, o1, T8a
  239.                         _MEMGET m, o, T8b
  240.                         _MEMPUT m, o1, T8b
  241.                         _MEMPUT m, o, T8a
  242.                         swapped = -1
  243.                     END IF
  244.                     i = i + 1
  245.                 LOOP UNTIL i + gap > EC
  246.             LOOP UNTIL gap = 1 AND swapped = 0
  247.         CASE 11: '_UNSIGNED _BYTE
  248.             DIM temp11(0 TO 255) AS _UNSIGNED LONG
  249.             DIM t11 AS _UNSIGNED _BYTE
  250.             i = 0
  251.             DO
  252.                 _MEMGET m, m.OFFSET + i, t11
  253.                 temp11(t11) = temp11(t11) + 1
  254.                 i = i + 1
  255.             LOOP UNTIL i > EC
  256.             i1 = 0
  257.             DO
  258.                 DO UNTIL temp11(i1) = 0
  259.                     _MEMPUT m, m.OFFSET + counter, i1 AS _UNSIGNED _BYTE
  260.                     counter = counter + 1
  261.                     temp11(i1) = temp11(i1) - 1
  262.                     IF counter > EC THEN EXIT SUB
  263.                 LOOP
  264.                 i1 = i1 + 1
  265.             LOOP UNTIL i1 > 255
  266.         CASE 12 '_UNSIGNED INTEGER
  267.             DIM temp12(0 TO 65535) AS _UNSIGNED LONG
  268.             DIM t12 AS _UNSIGNED INTEGER
  269.             i = 0
  270.             DO
  271.                 _MEMGET m, m.OFFSET + i * 2, t12
  272.                 temp12(t12) = temp12(t12) + 1
  273.                 i = i + 1
  274.             LOOP UNTIL i > EC
  275.             i1 = 0
  276.             DO
  277.                 DO UNTIL temp12(i1) = 0
  278.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS _UNSIGNED INTEGER
  279.                     counter = counter + 1
  280.                     temp12(i1) = temp12(i1) - 1
  281.                     IF counter > EC THEN EXIT SUB
  282.                 LOOP
  283.                 i1 = i1 + 1
  284.             LOOP UNTIL i1 > 65535
  285.         CASE 14 '_UNSIGNED LONG
  286.             DIM T14a AS _UNSIGNED LONG, T14b AS _UNSIGNED LONG
  287.             gap = EC
  288.             DO
  289.                 gap = 10 * gap \ 13
  290.                 IF gap < 1 THEN gap = 1
  291.                 i = 0
  292.                 swapped = 0
  293.                 DO
  294.                     o = m.OFFSET + i * 4
  295.                     o1 = m.OFFSET + (i + gap) * 4
  296.                     IF _MEMGET(m, o, _UNSIGNED LONG) > _MEMGET(m, o1, _UNSIGNED LONG) THEN
  297.                         _MEMGET m, o1, T14a
  298.                         _MEMGET m, o, T14b
  299.                         _MEMPUT m, o1, T14b
  300.                         _MEMPUT m, o, T14a
  301.                         swapped = -1
  302.                     END IF
  303.                     i = i + 1
  304.                 LOOP UNTIL i + gap > EC
  305.             LOOP UNTIL gap = 1 AND swapped = 0
  306.         CASE 18: '_UNSIGNED _INTEGER64
  307.             DIM T18a AS _UNSIGNED _INTEGER64, T18b AS _UNSIGNED _INTEGER64
  308.             gap = EC
  309.             DO
  310.                 gap = 10 * gap \ 13
  311.                 IF gap < 1 THEN gap = 1
  312.                 i = 0
  313.                 swapped = 0
  314.                 DO
  315.                     o = m.OFFSET + i * 8
  316.                     o1 = m.OFFSET + (i + gap) * 8
  317.                     IF _MEMGET(m, o, _UNSIGNED _INTEGER64) > _MEMGET(m, o1, _UNSIGNED _INTEGER64) THEN
  318.                         _MEMGET m, o1, T18a
  319.                         _MEMGET m, o, T18b
  320.                         _MEMPUT m, o1, T18b
  321.                         _MEMPUT m, o, T18a
  322.                         swapped = -1
  323.                     END IF
  324.                     i = i + 1
  325.                 LOOP UNTIL i + gap > EC
  326.             LOOP UNTIL gap = 1 AND swapped = 0
  327.     END SELECT
  329.  

Even with integer values and a fairly smallish data set (only 20,000 items), the load and sort method takes 5 seconds to run on my machine.  Loading then sorting takes about 0.6 seconds...

Now, part of the issue here is with opening the file for INPUT, which is slower than heck to process.  If we replace it with opening the file for BINARY access and using LINE INPUT and VAL, we change the times to  4.5 seconds and 0.15 seconds like so:

Code: QB64: [Select]
  1. CONST limit = 20000 'number of items to load and sort
  2.  
  3. DIM Array(limit) AS INTEGER
  4. DIM n(limit) AS INTEGER
  6. m = _MEM(Array())
  7. OPEN "temp.txt" FOR OUTPUT AS #1
  8. FOR i = 0 TO limit 'print a ton of entries
  9.     PRINT #1, RND * 10000
  12.  
  13.  
  14.  
  15.  
  16. OPEN "temp.txt" FOR BINARY AS #1
  17.  
  18. t## = TIMER
  19.  
  20. FOR i = 0 TO limit
  21.     LINE INPUT #1, temp$
  22.     num = VAL(temp$)
  23.     FOR j = 0 TO i - 1
  24.         IF num < n(j) THEN
  25.             FOR k = i TO j + 1 STEP -1
  26.                 n(k) = n(k - 1)
  27.             NEXT
  28.             EXIT FOR
  29.         END IF
  30.     NEXT
  31.     n(j) = num
  34. t1## = TIMER
  35.  
  36. PRINT USING "###.### seconds to load and sort together"; t1## - t##
  37.  
  38. t2## = TIMER
  39. OPEN "temp.txt" FOR BINARY AS #1
  40. FOR i = 0 TO limit
  41.     LINE INPUT #1, temp$
  42.     Array(i) = VAL(temp$)
  44. Sort m
  46. t3## = TIMER
  47. PRINT USING "###.### seconds to load and then sort"; t3## - t2##
  48.  
  49. FOR i = 0 TO limit STEP limit / 20 'and we'll print a selection of the data so we can compare results.
  50.     PRINT i, n(i), Array(i)
  51.     IF n(i) <> Array(i) THEN SLEEP
  53.  
  54.  
  55. SUB Sort (m AS _MEM)
  57.     $IF 64BIT THEN
  58.         DIM ES AS _INTEGER64, EC AS _INTEGER64
  59.     $ELSE
  60.         DIM ES AS LONG, EC AS LONG
  61.     $END IF
  62.  
  63.     IF NOT m.TYPE AND 65536 THEN EXIT SUB 'We won't work without an array
  64.     IF m.TYPE AND 1024 THEN DataType = 10
  65.     IF m.TYPE AND 1 THEN DataType = DataType + 1
  66.     IF m.TYPE AND 2 THEN DataType = DataType + 2
  67.     IF m.TYPE AND 4 THEN IF m.TYPE AND 128 THEN DataType = DataType + 4 ELSE DataType = 3
  68.     IF m.TYPE AND 8 THEN IF m.TYPE AND 128 THEN DataType = DataType + 8 ELSE DataType = 5
  69.     IF m.TYPE AND 32 THEN DataType = 6
  70.     IF m.TYPE AND 512 THEN DataType = 7
  71.  
  72.     'Convert our offset data over to something we can work with
  73.     DIM m1 AS _MEM: m1 = _MEMNEW(LEN(ES))
  74.     _MEMPUT m1, m1.OFFSET, m.ELEMENTSIZE: _MEMGET m1, m1.OFFSET, ES 'Element Size
  75.     _MEMPUT m1, m1.OFFSET, m.SIZE: _MEMGET m1, m1.OFFSET, EC 'Element Count will temporily hold the WHOLE array size
  76.     _MEMFREE m1
  77.  
  78.     EC = EC / ES - 1 'Now we take the whole element size / the size of the elements and get our actual element count.  We subtract 1 so our arrays start at 0 and not 1.
  79.     'And work with it!
  80.     DIM o AS _OFFSET, o1 AS _OFFSET, counter AS _UNSIGNED LONG
  81.  
  82.     SELECT CASE DataType
  83.         CASE 1 'BYTE
  84.             DIM temp1(-128 TO 127) AS _UNSIGNED LONG
  85.             DIM t1 AS _BYTE
  86.             i = 0
  87.             DO
  88.                 _MEMGET m, m.OFFSET + i, t1
  89.                 temp1(t1) = temp1(t1) + 1
  90.                 i = i + 1
  91.             LOOP UNTIL i > EC
  92.             i1 = -128
  93.             DO
  94.                 DO UNTIL temp1(i1) = 0
  95.                     _MEMPUT m, m.OFFSET + counter, i1 AS _BYTE
  96.                     counter = counter + 1
  97.                     temp1(i1) = temp1(i1) - 1
  98.                     IF counter > EC THEN EXIT SUB
  99.                 LOOP
  100.                 i1 = i1 + 1
  101.             LOOP UNTIL i1 > 127
  102.         CASE 2: 'INTEGER
  103.             DIM temp2(-32768 TO 32767) AS _UNSIGNED LONG
  104.             DIM t2 AS INTEGER
  105.             i = 0
  106.             DO
  107.                 _MEMGET m, m.OFFSET + i * 2, t2
  108.                 temp2(t2) = temp2(t2) + 1
  109.                 i = i + 1
  110.             LOOP UNTIL i > EC
  111.             i1 = -32768
  112.             DO
  113.                 DO UNTIL temp2(i1) = 0
  114.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS INTEGER
  115.                     counter = counter + 1
  116.                     temp2(i1) = temp2(i1) - 1
  117.                     IF counter > EC THEN EXIT SUB
  118.                 LOOP
  119.                 i1 = i1 + 1
  120.             LOOP UNTIL i1 > 32767
  121.         CASE 3 'SINGLE
  122.             DIM T3a AS SINGLE, T3b AS SINGLE
  123.             gap = EC
  124.             DO
  125.                 gap = 10 * gap \ 13
  126.                 IF gap < 1 THEN gap = 1
  127.                 i = 0
  128.                 swapped = 0
  129.                 DO
  130.                     o = m.OFFSET + i * 4
  131.                     o1 = m.OFFSET + (i + gap) * 4
  132.                     IF _MEMGET(m, o, SINGLE) > _MEMGET(m, o1, SINGLE) THEN
  133.                         _MEMGET m, o1, T3a
  134.                         _MEMGET m, o, T3b
  135.                         _MEMPUT m, o1, T3b
  136.                         _MEMPUT m, o, T3a
  137.                         swapped = -1
  138.                     END IF
  139.                     i = i + 1
  140.                 LOOP UNTIL i + gap > EC
  141.             LOOP UNTIL gap = 1 AND swapped = 0
  142.         CASE 4 'LONG
  143.             DIM T4a AS LONG, T4b AS LONG
  144.             gap = EC
  145.             DO
  146.                 gap = 10 * gap \ 13
  147.                 IF gap < 1 THEN gap = 1
  148.                 i = 0
  149.                 swapped = 0
  150.                 DO
  151.                     o = m.OFFSET + i * 4
  152.                     o1 = m.OFFSET + (i + gap) * 4
  153.                     IF _MEMGET(m, o, LONG) > _MEMGET(m, o1, LONG) THEN
  154.                         _MEMGET m, o1, T4a
  155.                         _MEMGET m, o, T4b
  156.                         _MEMPUT m, o1, T4b
  157.                         _MEMPUT m, o, T4a
  158.                         swapped = -1
  159.                     END IF
  160.                     i = i + 1
  161.                 LOOP UNTIL i + gap > EC
  162.             LOOP UNTIL gap = 1 AND swapped = 0
  163.         CASE 5 'DOUBLE
  164.             DIM T5a AS DOUBLE, T5b AS DOUBLE
  165.             gap = EC
  166.             DO
  167.                 gap = 10 * gap \ 13
  168.                 IF gap < 1 THEN gap = 1
  169.                 i = 0
  170.                 swapped = 0
  171.                 DO
  172.                     o = m.OFFSET + i * 8
  173.                     o1 = m.OFFSET + (i + gap) * 8
  174.                     IF _MEMGET(m, o, DOUBLE) > _MEMGET(m, o1, DOUBLE) THEN
  175.                         _MEMGET m, o1, T5a
  176.                         _MEMGET m, o, T5b
  177.                         _MEMPUT m, o1, T5b
  178.                         _MEMPUT m, o, T5a
  179.                         swapped = -1
  180.                     END IF
  181.                     i = i + 1
  182.                 LOOP UNTIL i + gap > EC
  183.             LOOP UNTIL gap = 1 AND swapped = 0
  184.         CASE 6 ' _FLOAT
  185.             DIM T6a AS _FLOAT, T6b AS _FLOAT
  186.             gap = EC
  187.             DO
  188.                 gap = 10 * gap \ 13
  189.                 IF gap < 1 THEN gap = 1
  190.                 i = 0
  191.                 swapped = 0
  192.                 DO
  193.                     o = m.OFFSET + i * 32
  194.                     o1 = m.OFFSET + (i + gap) * 32
  195.                     IF _MEMGET(m, o, _FLOAT) > _MEMGET(m, o1, _FLOAT) THEN
  196.                         _MEMGET m, o1, T6a
  197.                         _MEMGET m, o, T6b
  198.                         _MEMPUT m, o1, T6b
  199.                         _MEMPUT m, o, T6a
  200.                         swapped = -1
  201.                     END IF
  202.                     i = i + 1
  203.                 LOOP UNTIL i + gap > EC
  204.             LOOP UNTIL gap = 1 AND swapped = 0
  205.         CASE 7 'String
  206.             DIM T7a AS STRING, T7b AS STRING, T7c AS STRING
  207.             T7a = SPACE$(ES): T7b = SPACE$(ES): T7c = SPACE$(ES)
  208.             gap = EC
  209.             DO
  210.                 gap = INT(gap / 1.247330950103979)
  211.                 IF gap < 1 THEN gap = 1
  212.                 i = 0
  213.                 swapped = 0
  214.                 DO
  215.                     o = m.OFFSET + i * ES
  216.                     o1 = m.OFFSET + (i + gap) * ES
  217.                     _MEMGET m, o, T7a
  218.                     _MEMGET m, o1, T7b
  219.                     IF T7a > T7b THEN
  220.                         T7c = T7b
  221.                         _MEMPUT m, o1, T7a
  222.                         _MEMPUT m, o, T7c
  223.                         swapped = -1
  224.                     END IF
  225.                     i = i + 1
  226.                 LOOP UNTIL i + gap > EC
  227.             LOOP UNTIL gap = 1 AND swapped = false
  228.         CASE 8 '_INTEGER64
  229.             DIM T8a AS _INTEGER64, T8b AS _INTEGER64
  230.             gap = EC
  231.             DO
  232.                 gap = 10 * gap \ 13
  233.                 IF gap < 1 THEN gap = 1
  234.                 i = 0
  235.                 swapped = 0
  236.                 DO
  237.                     o = m.OFFSET + i * 8
  238.                     o1 = m.OFFSET + (i + gap) * 8
  239.                     IF _MEMGET(m, o, _INTEGER64) > _MEMGET(m, o1, _INTEGER64) THEN
  240.                         _MEMGET m, o1, T8a
  241.                         _MEMGET m, o, T8b
  242.                         _MEMPUT m, o1, T8b
  243.                         _MEMPUT m, o, T8a
  244.                         swapped = -1
  245.                     END IF
  246.                     i = i + 1
  247.                 LOOP UNTIL i + gap > EC
  248.             LOOP UNTIL gap = 1 AND swapped = 0
  249.         CASE 11: '_UNSIGNED _BYTE
  250.             DIM temp11(0 TO 255) AS _UNSIGNED LONG
  251.             DIM t11 AS _UNSIGNED _BYTE
  252.             i = 0
  253.             DO
  254.                 _MEMGET m, m.OFFSET + i, t11
  255.                 temp11(t11) = temp11(t11) + 1
  256.                 i = i + 1
  257.             LOOP UNTIL i > EC
  258.             i1 = 0
  259.             DO
  260.                 DO UNTIL temp11(i1) = 0
  261.                     _MEMPUT m, m.OFFSET + counter, i1 AS _UNSIGNED _BYTE
  262.                     counter = counter + 1
  263.                     temp11(i1) = temp11(i1) - 1
  264.                     IF counter > EC THEN EXIT SUB
  265.                 LOOP
  266.                 i1 = i1 + 1
  267.             LOOP UNTIL i1 > 255
  268.         CASE 12 '_UNSIGNED INTEGER
  269.             DIM temp12(0 TO 65535) AS _UNSIGNED LONG
  270.             DIM t12 AS _UNSIGNED INTEGER
  271.             i = 0
  272.             DO
  273.                 _MEMGET m, m.OFFSET + i * 2, t12
  274.                 temp12(t12) = temp12(t12) + 1
  275.                 i = i + 1
  276.             LOOP UNTIL i > EC
  277.             i1 = 0
  278.             DO
  279.                 DO UNTIL temp12(i1) = 0
  280.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS _UNSIGNED INTEGER
  281.                     counter = counter + 1
  282.                     temp12(i1) = temp12(i1) - 1
  283.                     IF counter > EC THEN EXIT SUB
  284.                 LOOP
  285.                 i1 = i1 + 1
  286.             LOOP UNTIL i1 > 65535
  287.         CASE 14 '_UNSIGNED LONG
  288.             DIM T14a AS _UNSIGNED LONG, T14b AS _UNSIGNED LONG
  289.             gap = EC
  290.             DO
  291.                 gap = 10 * gap \ 13
  292.                 IF gap < 1 THEN gap = 1
  293.                 i = 0
  294.                 swapped = 0
  295.                 DO
  296.                     o = m.OFFSET + i * 4
  297.                     o1 = m.OFFSET + (i + gap) * 4
  298.                     IF _MEMGET(m, o, _UNSIGNED LONG) > _MEMGET(m, o1, _UNSIGNED LONG) THEN
  299.                         _MEMGET m, o1, T14a
  300.                         _MEMGET m, o, T14b
  301.                         _MEMPUT m, o1, T14b
  302.                         _MEMPUT m, o, T14a
  303.                         swapped = -1
  304.                     END IF
  305.                     i = i + 1
  306.                 LOOP UNTIL i + gap > EC
  307.             LOOP UNTIL gap = 1 AND swapped = 0
  308.         CASE 18: '_UNSIGNED _INTEGER64
  309.             DIM T18a AS _UNSIGNED _INTEGER64, T18b AS _UNSIGNED _INTEGER64
  310.             gap = EC
  311.             DO
  312.                 gap = 10 * gap \ 13
  313.                 IF gap < 1 THEN gap = 1
  314.                 i = 0
  315.                 swapped = 0
  316.                 DO
  317.                     o = m.OFFSET + i * 8
  318.                     o1 = m.OFFSET + (i + gap) * 8
  319.                     IF _MEMGET(m, o, _UNSIGNED _INTEGER64) > _MEMGET(m, o1, _UNSIGNED _INTEGER64) THEN
  320.                         _MEMGET m, o1, T18a
  321.                         _MEMGET m, o, T18b
  322.                         _MEMPUT m, o1, T18b
  323.                         _MEMPUT m, o, T18a
  324.                         swapped = -1
  325.                     END IF
  326.                     i = i + 1
  327.                 LOOP UNTIL i + gap > EC
  328.             LOOP UNTIL gap = 1 AND swapped = 0
  329.     END SELECT
  331.  

In the time it takes us to load and sort 20000 numbers, we can instead load 500000 numbers and then sort them, as illustrated below:

Code: QB64: [Select]
  1. CONST limit = 500000 'number of items to load and sort
  2.  
  3. DIM Array(limit) AS INTEGER
  4. DIM n(limit) AS INTEGER
  6. m = _MEM(Array())
  7. OPEN "temp.txt" FOR OUTPUT AS #1
  8. FOR i = 0 TO limit 'print a ton of entries
  9.     PRINT #1, RND * 10000
  12.  
  13. OPEN "temp.txt" FOR BINARY AS #1
  14.  
  15. t## = TIMER
  16.  
  17. FOR i = 0 TO 20000
  18.     LINE INPUT #1, temp$
  19.     num = VAL(temp$)
  20.     FOR j = 0 TO i - 1
  21.         IF num < n(j) THEN
  22.             FOR k = i TO j + 1 STEP -1
  23.                 n(k) = n(k - 1)
  24.             NEXT
  25.             EXIT FOR
  26.         END IF
  27.     NEXT
  28.     n(j) = num
  31. t1## = TIMER
  32.  
  33. PRINT USING "###.### seconds to load and sort 20,000 items together"; t1## - t##
  34.  
  35.  
  36.  
  37. t2## = TIMER
  38. OPEN "temp.txt" FOR BINARY AS #1
  39. FOR i = 0 TO limit
  40.     LINE INPUT #1, temp$
  41.     Array(i) = VAL(temp$)
  43. Sort m
  45. t3## = TIMER
  46. PRINT USING "###.### seconds to load and then sort 500,000 items"; t3## - t2##
  47.  
  48. SUB Sort (m AS _MEM)
  50.     $IF 64BIT THEN
  51.         DIM ES AS _INTEGER64, EC AS _INTEGER64
  52.     $ELSE
  53.         DIM ES AS LONG, EC AS LONG
  54.     $END IF
  55.  
  56.     IF NOT m.TYPE AND 65536 THEN EXIT SUB 'We won't work without an array
  57.     IF m.TYPE AND 1024 THEN DataType = 10
  58.     IF m.TYPE AND 1 THEN DataType = DataType + 1
  59.     IF m.TYPE AND 2 THEN DataType = DataType + 2
  60.     IF m.TYPE AND 4 THEN IF m.TYPE AND 128 THEN DataType = DataType + 4 ELSE DataType = 3
  61.     IF m.TYPE AND 8 THEN IF m.TYPE AND 128 THEN DataType = DataType + 8 ELSE DataType = 5
  62.     IF m.TYPE AND 32 THEN DataType = 6
  63.     IF m.TYPE AND 512 THEN DataType = 7
  64.  
  65.     'Convert our offset data over to something we can work with
  66.     DIM m1 AS _MEM: m1 = _MEMNEW(LEN(ES))
  67.     _MEMPUT m1, m1.OFFSET, m.ELEMENTSIZE: _MEMGET m1, m1.OFFSET, ES 'Element Size
  68.     _MEMPUT m1, m1.OFFSET, m.SIZE: _MEMGET m1, m1.OFFSET, EC 'Element Count will temporily hold the WHOLE array size
  69.     _MEMFREE m1
  70.  
  71.     EC = EC / ES - 1 'Now we take the whole element size / the size of the elements and get our actual element count.  We subtract 1 so our arrays start at 0 and not 1.
  72.     'And work with it!
  73.     DIM o AS _OFFSET, o1 AS _OFFSET, counter AS _UNSIGNED LONG
  74.  
  75.     SELECT CASE DataType
  76.         CASE 1 'BYTE
  77.             DIM temp1(-128 TO 127) AS _UNSIGNED LONG
  78.             DIM t1 AS _BYTE
  79.             i = 0
  80.             DO
  81.                 _MEMGET m, m.OFFSET + i, t1
  82.                 temp1(t1) = temp1(t1) + 1
  83.                 i = i + 1
  84.             LOOP UNTIL i > EC
  85.             i1 = -128
  86.             DO
  87.                 DO UNTIL temp1(i1) = 0
  88.                     _MEMPUT m, m.OFFSET + counter, i1 AS _BYTE
  89.                     counter = counter + 1
  90.                     temp1(i1) = temp1(i1) - 1
  91.                     IF counter > EC THEN EXIT SUB
  92.                 LOOP
  93.                 i1 = i1 + 1
  94.             LOOP UNTIL i1 > 127
  95.         CASE 2: 'INTEGER
  96.             DIM temp2(-32768 TO 32767) AS _UNSIGNED LONG
  97.             DIM t2 AS INTEGER
  98.             i = 0
  99.             DO
  100.                 _MEMGET m, m.OFFSET + i * 2, t2
  101.                 temp2(t2) = temp2(t2) + 1
  102.                 i = i + 1
  103.             LOOP UNTIL i > EC
  104.             i1 = -32768
  105.             DO
  106.                 DO UNTIL temp2(i1) = 0
  107.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS INTEGER
  108.                     counter = counter + 1
  109.                     temp2(i1) = temp2(i1) - 1
  110.                     IF counter > EC THEN EXIT SUB
  111.                 LOOP
  112.                 i1 = i1 + 1
  113.             LOOP UNTIL i1 > 32767
  114.         CASE 3 'SINGLE
  115.             DIM T3a AS SINGLE, T3b AS SINGLE
  116.             gap = EC
  117.             DO
  118.                 gap = 10 * gap \ 13
  119.                 IF gap < 1 THEN gap = 1
  120.                 i = 0
  121.                 swapped = 0
  122.                 DO
  123.                     o = m.OFFSET + i * 4
  124.                     o1 = m.OFFSET + (i + gap) * 4
  125.                     IF _MEMGET(m, o, SINGLE) > _MEMGET(m, o1, SINGLE) THEN
  126.                         _MEMGET m, o1, T3a
  127.                         _MEMGET m, o, T3b
  128.                         _MEMPUT m, o1, T3b
  129.                         _MEMPUT m, o, T3a
  130.                         swapped = -1
  131.                     END IF
  132.                     i = i + 1
  133.                 LOOP UNTIL i + gap > EC
  134.             LOOP UNTIL gap = 1 AND swapped = 0
  135.         CASE 4 'LONG
  136.             DIM T4a AS LONG, T4b AS LONG
  137.             gap = EC
  138.             DO
  139.                 gap = 10 * gap \ 13
  140.                 IF gap < 1 THEN gap = 1
  141.                 i = 0
  142.                 swapped = 0
  143.                 DO
  144.                     o = m.OFFSET + i * 4
  145.                     o1 = m.OFFSET + (i + gap) * 4
  146.                     IF _MEMGET(m, o, LONG) > _MEMGET(m, o1, LONG) THEN
  147.                         _MEMGET m, o1, T4a
  148.                         _MEMGET m, o, T4b
  149.                         _MEMPUT m, o1, T4b
  150.                         _MEMPUT m, o, T4a
  151.                         swapped = -1
  152.                     END IF
  153.                     i = i + 1
  154.                 LOOP UNTIL i + gap > EC
  155.             LOOP UNTIL gap = 1 AND swapped = 0
  156.         CASE 5 'DOUBLE
  157.             DIM T5a AS DOUBLE, T5b AS DOUBLE
  158.             gap = EC
  159.             DO
  160.                 gap = 10 * gap \ 13
  161.                 IF gap < 1 THEN gap = 1
  162.                 i = 0
  163.                 swapped = 0
  164.                 DO
  165.                     o = m.OFFSET + i * 8
  166.                     o1 = m.OFFSET + (i + gap) * 8
  167.                     IF _MEMGET(m, o, DOUBLE) > _MEMGET(m, o1, DOUBLE) THEN
  168.                         _MEMGET m, o1, T5a
  169.                         _MEMGET m, o, T5b
  170.                         _MEMPUT m, o1, T5b
  171.                         _MEMPUT m, o, T5a
  172.                         swapped = -1
  173.                     END IF
  174.                     i = i + 1
  175.                 LOOP UNTIL i + gap > EC
  176.             LOOP UNTIL gap = 1 AND swapped = 0
  177.         CASE 6 ' _FLOAT
  178.             DIM T6a AS _FLOAT, T6b AS _FLOAT
  179.             gap = EC
  180.             DO
  181.                 gap = 10 * gap \ 13
  182.                 IF gap < 1 THEN gap = 1
  183.                 i = 0
  184.                 swapped = 0
  185.                 DO
  186.                     o = m.OFFSET + i * 32
  187.                     o1 = m.OFFSET + (i + gap) * 32
  188.                     IF _MEMGET(m, o, _FLOAT) > _MEMGET(m, o1, _FLOAT) THEN
  189.                         _MEMGET m, o1, T6a
  190.                         _MEMGET m, o, T6b
  191.                         _MEMPUT m, o1, T6b
  192.                         _MEMPUT m, o, T6a
  193.                         swapped = -1
  194.                     END IF
  195.                     i = i + 1
  196.                 LOOP UNTIL i + gap > EC
  197.             LOOP UNTIL gap = 1 AND swapped = 0
  198.         CASE 7 'String
  199.             DIM T7a AS STRING, T7b AS STRING, T7c AS STRING
  200.             T7a = SPACE$(ES): T7b = SPACE$(ES): T7c = SPACE$(ES)
  201.             gap = EC
  202.             DO
  203.                 gap = INT(gap / 1.247330950103979)
  204.                 IF gap < 1 THEN gap = 1
  205.                 i = 0
  206.                 swapped = 0
  207.                 DO
  208.                     o = m.OFFSET + i * ES
  209.                     o1 = m.OFFSET + (i + gap) * ES
  210.                     _MEMGET m, o, T7a
  211.                     _MEMGET m, o1, T7b
  212.                     IF T7a > T7b THEN
  213.                         T7c = T7b
  214.                         _MEMPUT m, o1, T7a
  215.                         _MEMPUT m, o, T7c
  216.                         swapped = -1
  217.                     END IF
  218.                     i = i + 1
  219.                 LOOP UNTIL i + gap > EC
  220.             LOOP UNTIL gap = 1 AND swapped = false
  221.         CASE 8 '_INTEGER64
  222.             DIM T8a AS _INTEGER64, T8b AS _INTEGER64
  223.             gap = EC
  224.             DO
  225.                 gap = 10 * gap \ 13
  226.                 IF gap < 1 THEN gap = 1
  227.                 i = 0
  228.                 swapped = 0
  229.                 DO
  230.                     o = m.OFFSET + i * 8
  231.                     o1 = m.OFFSET + (i + gap) * 8
  232.                     IF _MEMGET(m, o, _INTEGER64) > _MEMGET(m, o1, _INTEGER64) THEN
  233.                         _MEMGET m, o1, T8a
  234.                         _MEMGET m, o, T8b
  235.                         _MEMPUT m, o1, T8b
  236.                         _MEMPUT m, o, T8a
  237.                         swapped = -1
  238.                     END IF
  239.                     i = i + 1
  240.                 LOOP UNTIL i + gap > EC
  241.             LOOP UNTIL gap = 1 AND swapped = 0
  242.         CASE 11: '_UNSIGNED _BYTE
  243.             DIM temp11(0 TO 255) AS _UNSIGNED LONG
  244.             DIM t11 AS _UNSIGNED _BYTE
  245.             i = 0
  246.             DO
  247.                 _MEMGET m, m.OFFSET + i, t11
  248.                 temp11(t11) = temp11(t11) + 1
  249.                 i = i + 1
  250.             LOOP UNTIL i > EC
  251.             i1 = 0
  252.             DO
  253.                 DO UNTIL temp11(i1) = 0
  254.                     _MEMPUT m, m.OFFSET + counter, i1 AS _UNSIGNED _BYTE
  255.                     counter = counter + 1
  256.                     temp11(i1) = temp11(i1) - 1
  257.                     IF counter > EC THEN EXIT SUB
  258.                 LOOP
  259.                 i1 = i1 + 1
  260.             LOOP UNTIL i1 > 255
  261.         CASE 12 '_UNSIGNED INTEGER
  262.             DIM temp12(0 TO 65535) AS _UNSIGNED LONG
  263.             DIM t12 AS _UNSIGNED INTEGER
  264.             i = 0
  265.             DO
  266.                 _MEMGET m, m.OFFSET + i * 2, t12
  267.                 temp12(t12) = temp12(t12) + 1
  268.                 i = i + 1
  269.             LOOP UNTIL i > EC
  270.             i1 = 0
  271.             DO
  272.                 DO UNTIL temp12(i1) = 0
  273.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS _UNSIGNED INTEGER
  274.                     counter = counter + 1
  275.                     temp12(i1) = temp12(i1) - 1
  276.                     IF counter > EC THEN EXIT SUB
  277.                 LOOP
  278.                 i1 = i1 + 1
  279.             LOOP UNTIL i1 > 65535
  280.         CASE 14 '_UNSIGNED LONG
  281.             DIM T14a AS _UNSIGNED LONG, T14b AS _UNSIGNED LONG
  282.             gap = EC
  283.             DO
  284.                 gap = 10 * gap \ 13
  285.                 IF gap < 1 THEN gap = 1
  286.                 i = 0
  287.                 swapped = 0
  288.                 DO
  289.                     o = m.OFFSET + i * 4
  290.                     o1 = m.OFFSET + (i + gap) * 4
  291.                     IF _MEMGET(m, o, _UNSIGNED LONG) > _MEMGET(m, o1, _UNSIGNED LONG) THEN
  292.                         _MEMGET m, o1, T14a
  293.                         _MEMGET m, o, T14b
  294.                         _MEMPUT m, o1, T14b
  295.                         _MEMPUT m, o, T14a
  296.                         swapped = -1
  297.                     END IF
  298.                     i = i + 1
  299.                 LOOP UNTIL i + gap > EC
  300.             LOOP UNTIL gap = 1 AND swapped = 0
  301.         CASE 18: '_UNSIGNED _INTEGER64
  302.             DIM T18a AS _UNSIGNED _INTEGER64, T18b AS _UNSIGNED _INTEGER64
  303.             gap = EC
  304.             DO
  305.                 gap = 10 * gap \ 13
  306.                 IF gap < 1 THEN gap = 1
  307.                 i = 0
  308.                 swapped = 0
  309.                 DO
  310.                     o = m.OFFSET + i * 8
  311.                     o1 = m.OFFSET + (i + gap) * 8
  312.                     IF _MEMGET(m, o, _UNSIGNED _INTEGER64) > _MEMGET(m, o1, _UNSIGNED _INTEGER64) THEN
  313.                         _MEMGET m, o1, T18a
  314.                         _MEMGET m, o, T18b
  315.                         _MEMPUT m, o1, T18b
  316.                         _MEMPUT m, o, T18a
  317.                         swapped = -1
  318.                     END IF
  319.                     i = i + 1
  320.                 LOOP UNTIL i + gap > EC
  321.             LOOP UNTIL gap = 1 AND swapped = 0
  322.     END SELECT
  324.  


Loading and sorting as you go works good for small data sets, but what you're really implementing is an Insertion Sort method, and there's a lot of other sorting routines which are much more efficient out there.  The more data you need to add into an array, the less useful an insertion sort method becomes.  If you have 100,000 sorted items and need to add a new sorted item into the set, then it's definitely the way to go.  If you have 100,000 items that all need to be sorted completely to begin with, then you should generally choose a more efficient sorting method.

Since the memsort routine is a standard part of my toolbox, I almost never bother with the "load and sort" method.  I generally just load an array and then sort it and be done with it, like the examples above.  ;)


And just for fun, and to really highlight the difference in various sorting methods performance, I took the file loading times completely out and wrote this little demo:

Code: QB64: [Select]
  1. CONST limit = 2000000 'number of items to load and sort
  2.  
  3. DIM Array(limit) AS INTEGER
  4. DIM n(limit) AS INTEGER
  6. m = _MEM(Array())
  7.  
  8. FOR i = 0 TO limit 'print a ton of entries
  9.     num = RND * 100000
  10.     n(i) = num
  11.     Array(i) = num
  14.  
  15. t## = TIMER
  16.  
  17. FOR i = 0 TO 20000
  18.     num = n(i)
  19.     FOR j = 0 TO i - 1
  20.         IF num < n(j) THEN
  21.             FOR k = i TO j + 1 STEP -1
  22.                 n(k) = n(k - 1)
  23.             NEXT
  24.             EXIT FOR
  25.         END IF
  26.     NEXT
  27.     n(j) = num
  29. t1## = TIMER
  30.  
  31. PRINT USING "###.### seconds to insertion sort 20,000 items together"; t1## - t##
  32.  
  33.  
  34.  
  35. t2## = TIMER(0.00001)
  36. Sort m
  37. t3## = TIMER(0.00001)
  38. PRINT USING "###.### seconds to mem sort 2,000,000 items"; t3## - t2##
  39.  
  40. SUB Sort (m AS _MEM)
  42.     $IF 64BIT THEN
  43.         DIM ES AS _INTEGER64, EC AS _INTEGER64
  44.     $ELSE
  45.         DIM ES AS LONG, EC AS LONG
  46.     $END IF
  47.  
  48.     IF NOT m.TYPE AND 65536 THEN EXIT SUB 'We won't work without an array
  49.     IF m.TYPE AND 1024 THEN DataType = 10
  50.     IF m.TYPE AND 1 THEN DataType = DataType + 1
  51.     IF m.TYPE AND 2 THEN DataType = DataType + 2
  52.     IF m.TYPE AND 4 THEN IF m.TYPE AND 128 THEN DataType = DataType + 4 ELSE DataType = 3
  53.     IF m.TYPE AND 8 THEN IF m.TYPE AND 128 THEN DataType = DataType + 8 ELSE DataType = 5
  54.     IF m.TYPE AND 32 THEN DataType = 6
  55.     IF m.TYPE AND 512 THEN DataType = 7
  56.  
  57.     'Convert our offset data over to something we can work with
  58.     DIM m1 AS _MEM: m1 = _MEMNEW(LEN(ES))
  59.     _MEMPUT m1, m1.OFFSET, m.ELEMENTSIZE: _MEMGET m1, m1.OFFSET, ES 'Element Size
  60.     _MEMPUT m1, m1.OFFSET, m.SIZE: _MEMGET m1, m1.OFFSET, EC 'Element Count will temporily hold the WHOLE array size
  61.     _MEMFREE m1
  62.  
  63.     EC = EC / ES - 1 'Now we take the whole element size / the size of the elements and get our actual element count.  We subtract 1 so our arrays start at 0 and not 1.
  64.     'And work with it!
  65.     DIM o AS _OFFSET, o1 AS _OFFSET, counter AS _UNSIGNED LONG
  66.  
  67.     SELECT CASE DataType
  68.         CASE 1 'BYTE
  69.             DIM temp1(-128 TO 127) AS _UNSIGNED LONG
  70.             DIM t1 AS _BYTE
  71.             i = 0
  72.             DO
  73.                 _MEMGET m, m.OFFSET + i, t1
  74.                 temp1(t1) = temp1(t1) + 1
  75.                 i = i + 1
  76.             LOOP UNTIL i > EC
  77.             i1 = -128
  78.             DO
  79.                 DO UNTIL temp1(i1) = 0
  80.                     _MEMPUT m, m.OFFSET + counter, i1 AS _BYTE
  81.                     counter = counter + 1
  82.                     temp1(i1) = temp1(i1) - 1
  83.                     IF counter > EC THEN EXIT SUB
  84.                 LOOP
  85.                 i1 = i1 + 1
  86.             LOOP UNTIL i1 > 127
  87.         CASE 2: 'INTEGER
  88.             DIM temp2(-32768 TO 32767) AS _UNSIGNED LONG
  89.             DIM t2 AS INTEGER
  90.             i = 0
  91.             DO
  92.                 _MEMGET m, m.OFFSET + i * 2, t2
  93.                 temp2(t2) = temp2(t2) + 1
  94.                 i = i + 1
  95.             LOOP UNTIL i > EC
  96.             i1 = -32768
  97.             DO
  98.                 DO UNTIL temp2(i1) = 0
  99.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS INTEGER
  100.                     counter = counter + 1
  101.                     temp2(i1) = temp2(i1) - 1
  102.                     IF counter > EC THEN EXIT SUB
  103.                 LOOP
  104.                 i1 = i1 + 1
  105.             LOOP UNTIL i1 > 32767
  106.         CASE 3 'SINGLE
  107.             DIM T3a AS SINGLE, T3b AS SINGLE
  108.             gap = EC
  109.             DO
  110.                 gap = 10 * gap \ 13
  111.                 IF gap < 1 THEN gap = 1
  112.                 i = 0
  113.                 swapped = 0
  114.                 DO
  115.                     o = m.OFFSET + i * 4
  116.                     o1 = m.OFFSET + (i + gap) * 4
  117.                     IF _MEMGET(m, o, SINGLE) > _MEMGET(m, o1, SINGLE) THEN
  118.                         _MEMGET m, o1, T3a
  119.                         _MEMGET m, o, T3b
  120.                         _MEMPUT m, o1, T3b
  121.                         _MEMPUT m, o, T3a
  122.                         swapped = -1
  123.                     END IF
  124.                     i = i + 1
  125.                 LOOP UNTIL i + gap > EC
  126.             LOOP UNTIL gap = 1 AND swapped = 0
  127.         CASE 4 'LONG
  128.             DIM T4a AS LONG, T4b AS LONG
  129.             gap = EC
  130.             DO
  131.                 gap = 10 * gap \ 13
  132.                 IF gap < 1 THEN gap = 1
  133.                 i = 0
  134.                 swapped = 0
  135.                 DO
  136.                     o = m.OFFSET + i * 4
  137.                     o1 = m.OFFSET + (i + gap) * 4
  138.                     IF _MEMGET(m, o, LONG) > _MEMGET(m, o1, LONG) THEN
  139.                         _MEMGET m, o1, T4a
  140.                         _MEMGET m, o, T4b
  141.                         _MEMPUT m, o1, T4b
  142.                         _MEMPUT m, o, T4a
  143.                         swapped = -1
  144.                     END IF
  145.                     i = i + 1
  146.                 LOOP UNTIL i + gap > EC
  147.             LOOP UNTIL gap = 1 AND swapped = 0
  148.         CASE 5 'DOUBLE
  149.             DIM T5a AS DOUBLE, T5b AS DOUBLE
  150.             gap = EC
  151.             DO
  152.                 gap = 10 * gap \ 13
  153.                 IF gap < 1 THEN gap = 1
  154.                 i = 0
  155.                 swapped = 0
  156.                 DO
  157.                     o = m.OFFSET + i * 8
  158.                     o1 = m.OFFSET + (i + gap) * 8
  159.                     IF _MEMGET(m, o, DOUBLE) > _MEMGET(m, o1, DOUBLE) THEN
  160.                         _MEMGET m, o1, T5a
  161.                         _MEMGET m, o, T5b
  162.                         _MEMPUT m, o1, T5b
  163.                         _MEMPUT m, o, T5a
  164.                         swapped = -1
  165.                     END IF
  166.                     i = i + 1
  167.                 LOOP UNTIL i + gap > EC
  168.             LOOP UNTIL gap = 1 AND swapped = 0
  169.         CASE 6 ' _FLOAT
  170.             DIM T6a AS _FLOAT, T6b AS _FLOAT
  171.             gap = EC
  172.             DO
  173.                 gap = 10 * gap \ 13
  174.                 IF gap < 1 THEN gap = 1
  175.                 i = 0
  176.                 swapped = 0
  177.                 DO
  178.                     o = m.OFFSET + i * 32
  179.                     o1 = m.OFFSET + (i + gap) * 32
  180.                     IF _MEMGET(m, o, _FLOAT) > _MEMGET(m, o1, _FLOAT) THEN
  181.                         _MEMGET m, o1, T6a
  182.                         _MEMGET m, o, T6b
  183.                         _MEMPUT m, o1, T6b
  184.                         _MEMPUT m, o, T6a
  185.                         swapped = -1
  186.                     END IF
  187.                     i = i + 1
  188.                 LOOP UNTIL i + gap > EC
  189.             LOOP UNTIL gap = 1 AND swapped = 0
  190.         CASE 7 'String
  191.             DIM T7a AS STRING, T7b AS STRING, T7c AS STRING
  192.             T7a = SPACE$(ES): T7b = SPACE$(ES): T7c = SPACE$(ES)
  193.             gap = EC
  194.             DO
  195.                 gap = INT(gap / 1.247330950103979)
  196.                 IF gap < 1 THEN gap = 1
  197.                 i = 0
  198.                 swapped = 0
  199.                 DO
  200.                     o = m.OFFSET + i * ES
  201.                     o1 = m.OFFSET + (i + gap) * ES
  202.                     _MEMGET m, o, T7a
  203.                     _MEMGET m, o1, T7b
  204.                     IF T7a > T7b THEN
  205.                         T7c = T7b
  206.                         _MEMPUT m, o1, T7a
  207.                         _MEMPUT m, o, T7c
  208.                         swapped = -1
  209.                     END IF
  210.                     i = i + 1
  211.                 LOOP UNTIL i + gap > EC
  212.             LOOP UNTIL gap = 1 AND swapped = false
  213.         CASE 8 '_INTEGER64
  214.             DIM T8a AS _INTEGER64, T8b AS _INTEGER64
  215.             gap = EC
  216.             DO
  217.                 gap = 10 * gap \ 13
  218.                 IF gap < 1 THEN gap = 1
  219.                 i = 0
  220.                 swapped = 0
  221.                 DO
  222.                     o = m.OFFSET + i * 8
  223.                     o1 = m.OFFSET + (i + gap) * 8
  224.                     IF _MEMGET(m, o, _INTEGER64) > _MEMGET(m, o1, _INTEGER64) THEN
  225.                         _MEMGET m, o1, T8a
  226.                         _MEMGET m, o, T8b
  227.                         _MEMPUT m, o1, T8b
  228.                         _MEMPUT m, o, T8a
  229.                         swapped = -1
  230.                     END IF
  231.                     i = i + 1
  232.                 LOOP UNTIL i + gap > EC
  233.             LOOP UNTIL gap = 1 AND swapped = 0
  234.         CASE 11: '_UNSIGNED _BYTE
  235.             DIM temp11(0 TO 255) AS _UNSIGNED LONG
  236.             DIM t11 AS _UNSIGNED _BYTE
  237.             i = 0
  238.             DO
  239.                 _MEMGET m, m.OFFSET + i, t11
  240.                 temp11(t11) = temp11(t11) + 1
  241.                 i = i + 1
  242.             LOOP UNTIL i > EC
  243.             i1 = 0
  244.             DO
  245.                 DO UNTIL temp11(i1) = 0
  246.                     _MEMPUT m, m.OFFSET + counter, i1 AS _UNSIGNED _BYTE
  247.                     counter = counter + 1
  248.                     temp11(i1) = temp11(i1) - 1
  249.                     IF counter > EC THEN EXIT SUB
  250.                 LOOP
  251.                 i1 = i1 + 1
  252.             LOOP UNTIL i1 > 255
  253.         CASE 12 '_UNSIGNED INTEGER
  254.             DIM temp12(0 TO 65535) AS _UNSIGNED LONG
  255.             DIM t12 AS _UNSIGNED INTEGER
  256.             i = 0
  257.             DO
  258.                 _MEMGET m, m.OFFSET + i * 2, t12
  259.                 temp12(t12) = temp12(t12) + 1
  260.                 i = i + 1
  261.             LOOP UNTIL i > EC
  262.             i1 = 0
  263.             DO
  264.                 DO UNTIL temp12(i1) = 0
  265.                     _MEMPUT m, m.OFFSET + counter * 2, i1 AS _UNSIGNED INTEGER
  266.                     counter = counter + 1
  267.                     temp12(i1) = temp12(i1) - 1
  268.                     IF counter > EC THEN EXIT SUB
  269.                 LOOP
  270.                 i1 = i1 + 1
  271.             LOOP UNTIL i1 > 65535
  272.         CASE 14 '_UNSIGNED LONG
  273.             DIM T14a AS _UNSIGNED LONG, T14b AS _UNSIGNED LONG
  274.             gap = EC
  275.             DO
  276.                 gap = 10 * gap \ 13
  277.                 IF gap < 1 THEN gap = 1
  278.                 i = 0
  279.                 swapped = 0
  280.                 DO
  281.                     o = m.OFFSET + i * 4
  282.                     o1 = m.OFFSET + (i + gap) * 4
  283.                     IF _MEMGET(m, o, _UNSIGNED LONG) > _MEMGET(m, o1, _UNSIGNED LONG) THEN
  284.                         _MEMGET m, o1, T14a
  285.                         _MEMGET m, o, T14b
  286.                         _MEMPUT m, o1, T14b
  287.                         _MEMPUT m, o, T14a
  288.                         swapped = -1
  289.                     END IF
  290.                     i = i + 1
  291.                 LOOP UNTIL i + gap > EC
  292.             LOOP UNTIL gap = 1 AND swapped = 0
  293.         CASE 18: '_UNSIGNED _INTEGER64
  294.             DIM T18a AS _UNSIGNED _INTEGER64, T18b AS _UNSIGNED _INTEGER64
  295.             gap = EC
  296.             DO
  297.                 gap = 10 * gap \ 13
  298.                 IF gap < 1 THEN gap = 1
  299.                 i = 0
  300.                 swapped = 0
  301.                 DO
  302.                     o = m.OFFSET + i * 8
  303.                     o1 = m.OFFSET + (i + gap) * 8
  304.                     IF _MEMGET(m, o, _UNSIGNED _INTEGER64) > _MEMGET(m, o1, _UNSIGNED _INTEGER64) THEN
  305.                         _MEMGET m, o1, T18a
  306.                         _MEMGET m, o, T18b
  307.                         _MEMPUT m, o1, T18b
  308.                         _MEMPUT m, o, T18a
  309.                         swapped = -1
  310.                     END IF
  311.                     i = i + 1
  312.                 LOOP UNTIL i + gap > EC
  313.             LOOP UNTIL gap = 1 AND swapped = 0
  314.     END SELECT
  316.  

4.34 seconds to insertion sort 20,000 items together.
0.14 seconds to mem sort 2,000,000 items together.

30 times faster, and we sorted 100 times more items...  I think that goes to show why generally speaking, I prefer to just load the array and then sort the array.  ;)
Title: Re: Top 10 Algorythm
Post by: Dimster on November 04, 2019, 08:49:38 am
Thanks very much - a lot of very helpful approaches - looking forward to trying them all.

My spelling of Algorythm is deliberate. It helps to remind me there needs to be a rythm to my coding - smooth and simple and flowing. Coding on the other hand implies to me blocks, staunch and static. I like to feel I'm an artist bringing a useful screen to life as opposed to a worker bee plugging in tried a true methods and rules. One of those nuts who likes the imaginative part to of programming. You guys and girls on this forum do Algorythms - amazing creative minds  - as TempodiBasic would say, this is IMHO.
Title: Re: Top 10 Algorythm
Post by: Qwerkey on November 04, 2019, 10:33:24 am
Quote from: Dimster on November 04, 2019, 08:49:38 am
My spelling of Algorythm is deliberate.

Apologies Dimster.  I acknowledge your clever creation of the portmanteau word.  But when I look at it, all I see is it shouting "change my y to an i"!!
Title: Re: Top 10 Algorythm
Post by: bplus on November 04, 2019, 11:39:21 am
;-)) Steve, you have a wonderful well worked-out hammer and you are looking for a nail!

Dimster, you probably have high hopes for your game but let me know when you get to 20,000 players to justify adding 275+ lines for a great Sort routine :D

Also, I didn't even notice the fanciful wordplay until Qwerkey mentioned it, I don't know can I blame it on poor eyesight?

portmanteau - so that is what that is! ;)
Title: Re: Top 10 Algorythm
Post by: Dimster on November 04, 2019, 11:55:26 am
I could change the Y to an I but I like Quirky.
Title: Re: Top 10 Algorythm
Post by: SMcNeill on November 04, 2019, 02:35:49 pm
Quote from: bplus on November 04, 2019, 11:39:21 am
;-)) Steve, you have a wonderful well worked-out hammer and you are looking for a nail!

Dimster, you probably have high hopes for your game but let me know when you get to 20,000 players to justify adding 275+ lines for a great Sort routine :D

You don't have to add 275 lines for a great sort. I just tend to plug in the memsort routine as it's one which works with all the various data types out there (with the exception of variable length strings).  I don't constantly retype those lines; I just copy/paste them from my toolbox.  :P

If we break the memsort down to its basic form, what we have is a combsort such as the following, which comes in at only 15 lines:

Code: QB64: [Select]
  1. gap = UBOUND(Array)
  3.     gap = 10 * gap \ 13
  4.     IF gap < 1 THEN gap = 1
  5.     i = 0
  6.     swapped = 0
  7.     DO
  8.         IF Array(i) < WordCount(i + gap) THEN
  9.             SWAP Array(i), Array(i + gap)
  10.             SWAP Array(i), Array(i + gap)
  11.             swapped = -1
  12.         END IF
  13.         i = i + 1
  14.     LOOP UNTIL i + gap > UBOUND(Array)
  15. LOOP UNTIL gap = 1 AND swapped = 0
Title: Re: Top 10 Algorythm
Post by: Calloway on November 04, 2019, 10:51:35 pm
If you're only finding top 10 then why are you keeping all the other data?
Title: Re: Top 10 Algorythm
Post by: SMcNeill on November 04, 2019, 11:11:29 pm
Quote from: Calloway on November 04, 2019, 10:51:35 pm
If you're only finding top 10 then why are you keeping all the other data?

Ranking boards would be the obvious answer.   Take a game where you count wins as +2 points and losses as -1 point for your score...

Joe plays 20 games and wins 15, loses 5.  He’s the number 10 player with 25 points....

Unless you track the other player’s data, there’s no way for anyone to ever beat Joe’s top 10 score.   You start, you win, you get 2 points — not enough for top 10, so your score is discarded...

You might want the top 10 so you can give them a free month’s game subscription, invite them to play test the next beta version, or just recognize them with a badge on the leader boards, but you’d still want to keep everyone’s data to calculate their rankings.
Title: Re: Top 10 Algorythm
Post by: MLambert on November 05, 2019, 03:27:41 am
cmsort.exe allows me to collate data, in the millions of records, within seconds.

Try it
Title: Re: Top 10 Algorythm
Post by: TempodiBasic on November 06, 2019, 05:39:58 am
I can affirm that the Steve's solution is better because it is for  Beginner's All-Purpose Simbolic Instruction Code...
you can load any huge amount of data list and process it in few seconds, and it is for All-purpose because you can search the first, the first three or the first one hundred!

I don't know if Bplus can _MEMorize this my sentence or leave the hammer in the toolbox.
The solution of Steve go behind the issue of the first 3 players with higher score and arrive to solve the issue having huge undefined data score how can I find the kvariable first players with higher score?

That's my IMHO
Text Only | Text with Attachments