QBasic / QB64 Discussion Forum      Other Subforums, Links and Downloads
 

 Return to Index  

Variation of Shuffle Sort algorithm

April 10 2008 at 8:00 PM
Solitaire  (Login Solitaire1)
R


Response to comparison

 
I rearranged the sort so it saves the selected number in ascending order of the array index starting from the beginning, instead of in reverse which started from the end.

You may notice that since only the numbers up to "picks" is shuffled, the numbers that weren't selected are mostly still in sequential order, except for the randomly selected and swapped indexes. In any case, there are no duplicates and every number is included in the entire range. When a small number of selections is needed among a large range, this modified algorithm is more efficient than the original Shuffle Sort, which repeats as many times as the entire range.

Actually, we've come full circle. The only real difference between this modified version and the original version of the Shuffle Sort is that the second FOR loop only goes up to the number of selections ("picks") instead of the full range. The demo version started by Montrealer shows how the mechanism works step by step.

===============================================================================
'Shuffle Sort originally posted by Solitaire.
'Demonstration version started by Montrealer  (Modified and revised by Solitaire)
'Selections are now placed in numbered order of array indexes, not in reverse order
'Note: Same index may be selected randomly more than once, but after being
'      swapped, it will now contain a different value.

DIM picks AS INTEGER, range AS INTEGER
DIM index AS INTEGER, x AS INTEGER
CLS
RANDOMIZE TIMER
range = 40                              'entire range
picks = 10                              'number of selections
DIM numbers(range) AS INTEGER

FOR x = 1 TO range                      'assign sequential values to array
    numbers(x) = x
NEXT x

PRINT "Partial Shuffle Sort:"
PRINT
FOR x = 1 TO picks                      'only shuffles up to the number of selections
    index = INT(RND * range) + 1        'value at random index will be swapped
    PRINT TAB(10); numbers(index), "goes to position:"; x
    SWAP numbers(index), numbers(x)     'swaps value in order of array index
NEXT x

PRINT : PRINT "Numbers selected, in sequence:"
FOR x = 1 TO picks
    PRINT numbers(x);
NEXT x

PRINT : PRINT : PRINT "Numbers not selected:"
FOR x = picks + 1 TO range
    PRINT numbers(x);
NEXT x
SYSTEM



    
This message has been edited by Solitaire1 on Apr 10, 2008 9:28 PM
This message has been edited by Solitaire1 on Apr 10, 2008 9:18 PM
This message has been edited by Solitaire1 on Apr 10, 2008 8:14 PM


 
 Respond to this message   
Responses

 Copyright © 1999-2014 Network54. All rights reserved.   Terms of Use   Privacy Statement