• Print

Author Topic: rearranging arrays  (Read 277 times)

23452

  • Jr. Member
  • **
  • Posts: 72
    • Email
rearranging arrays
« on: October 20, 2012, 09:15:35 PM »
Is there a function to rearrange arrays by there values?
ex.
array(0) = 4
array(1) = 11
array(2) = 9
array(3) = 6
Becoming
array(0) = 4
array(1) = 6
array(2) = 9
array(3) = 11
Or do it form highest to lowest

23452

  • Jr. Member
  • **
  • Posts: 72
    • Email
Re: rearranging arrays
« Reply #1 on: October 20, 2012, 09:19:12 PM »
I have an idea of how to do it in the code, but it world take way to long.

TerryRitchie

  • Hero Member
  • *****
  • Posts: 2264
  • FORMAT C:\ /Q /U /AUTOTEST (How to repair Win8)
    • Email
Re: rearranging arrays
« Reply #2 on: October 20, 2012, 09:57:48 PM »
There are many sorting algorithms in the forum.  Use search to see if you can find some of them.  It's late, otherwise I would be of more help.

You can also search the forum and net for "bubble sort", the easiest way (but one of the slowest) to sort something like this.

SMcNeill

  • Hero Member
  • *****
  • Posts: 2414
    • Email
Re: rearranging arrays
« Reply #3 on: October 21, 2012, 03:33:13 AM »
Copies from my QBDbase topic:


Code: [Select]
limit = 100000

DIM x(limit) AS _INTEGER64
RANDOMIZE TIMER
PRINT "Initializing Data"
FOR i = 0 TO limit
    x(i) = RND(1) * 1234567890987654321
NEXT


t# = TIMER(0.001)


PRINT "Bubble Sorting Data": bubblesort x()
'PRINT "Comb Sorting Data" : combsort x()

t1# = TIMER(0.001)
PRINT USING "Data Sorted in ##,###.##### seconds."; t1# - t#
SLEEP
stepper = 20

FOR i = 0 TO limit - stepper STEP stepper
    FOR j = i TO i + stepper
        PRINT x(j)
    NEXT
    'SLEEP
NEXT


SUB combsort (array() AS _INTEGER64)
gap = UBOUND(array)

DO
    gap = INT(gap / 1.247330950103979)
    IF gap < 1 THEN gap = 1
    i = 0
    swapped = false
    DO
        IF array(i) > array(i + gap) THEN
            SWAP array(i), array(i + gap)
            swapped = true
        END IF
        i = i + 1
    LOOP UNTIL i + gap > UBOUND(array)
LOOP UNTIL gap = 1 AND swapped = false
END SUB

SUB bubblesort (array() AS _INTEGER64)
nr = UBOUND(array)
FOR k = 1 TO nr
    FOR i = k TO nr
        IF array(k) > array(i) THEN SWAP array(k), array(i)
    NEXT
NEXT
END SUB

Try it first as it is, and be patient.  Bubblesort takes about 3 minutes on my machine, and I've got a fast set-up here.  Start it, and then go eat a cookie...

See how long it takes?  This is with ONLY 100,000 comparisons.  Move it up to 1,000,000 and the times go up exponentially!  A very inefficient way to sort (but it's so darn simple to code!)

Now remark out the line PRINTING "Bubble Sort Method", and unremark the line below it.  Give it a run.

See any difference in speed?

*****************************

This illustrates bubble sort and comb sort methods, and the difference in performance in the two.  This works with string arrays, but is easy enough to modify if you need it for numeric ones.
http://bit.ly/TextImage -- Library of QB64 code to manipulate text and images, as a BM library.
http://bit.ly/Color32 -- A set of color CONST for use in 32 bit mode, as a BI library.

http://bit.ly/DataToDrive - A set of routines to quickly and easily get data to and from the disk.  BI and BM files

Gorlock

  • Sr. Member
  • ****
  • Posts: 337
    • Email
Re: rearranging arrays
« Reply #4 on: October 21, 2012, 01:11:22 PM »
Try something like this:

Code: [Select]
REDIM array(3)

array(0) = 4
array(1) = 11
array(2) = 9
array(3) = 6


FOR x = 0 TO UBOUND(array)
    FOR y = 0 TO UBOUND(array)
        IF array(x) < array(y) AND x <> y THEN SWAP array(y), array(x)
NEXT y, x

FOR r = 0 TO UBOUND(array)
    PRINT array(r)
NEXT r

DarthWho

  • Hero Member
  • *****
  • Posts: 3853
  • Timelord of the Sith
Re: rearranging arrays
« Reply #5 on: October 21, 2012, 01:23:53 PM »
well Eordeson created a program comparing various sorting algorithms:
http://www.qb64.net/forum/index.php?topic=5038.msg52201#msg52201

there is always the option of if you are dealing with integers of using counting sort:
Code: [Select]
items = 30
DIM k(items - 1) AS INTEGER
'fill k
'for simplicity's sake 10 is max 0 is min provides guarantee of duplication
RANDOMIZE TIMER
maxval = 10
PRINT "unsorted";
FOR I = 0 TO items - 1
    k(I) = INT((maxval + 1) * RND)
    PRINT STR$(k(I));
NEXT I
DIM cnt(0 TO maxval)
FOR I = 0 TO items - 1
    cnt(k(I)) = cnt(k(I)) + 1
NEXT I
FOR I = 0 TO maxval
    c = cnt(I)
    cnt(I) = tot
    tot = tot + c
NEXT I
DIM outt(items - 1)
PRINT
PRINT "sorted";
FOR I = 0 TO items - 1
    outt(cnt(k(I))) = k(I)
    cnt(k(I)) = cnt(k(I)) + 1
NEXT I
FOR I = 0 TO items - 1
    PRINT STR$(outt(I));
NEXT I

then there is my hybrid sort Shunt sort:
Code: [Select]
'shunt sort

items = 200
TYPE Petrichor
    a AS SINGLE
    b AS INTEGER
END TYPE
DIM k(items) AS Petrichor
'fill k
SCREEN 12
'idealrange% = 7.8126 * items - 444.19
'for simplicity's sake 10 is max 0 is min provides guarantee of duplication
RANDOMIZE TIMER
maxval = 21
IF items > 60 THEN
    idealrange% = 7.8126 * items - 444.19
ELSE
    idealrange% = maxval
END IF
fgmt = idealrange% / maxval
'PRINT "unsorted";
FOR i = 0 TO items - 1
    k(i).a = RND * maxval '(maxval - maxval * (i / items)) '* (I / items) * ABS(SIN(I / items))) '* RND '(maxval) * RND)
    k(i).b = INT(k(i).a * fgmt)
    PSET (i, (maxval - k(i).a) * 15), 15
    'PRINT STR$(k(I).a);
NEXT i
DIM cnt(-1 TO maxval * fgmt + 1) '* fgmt + 1)
FOR i = 0 TO items - 1
    cnt(k(i).b) = cnt(k(i).b) + 1
NEXT i
'IF 4 <= 2 THEN k = 3
FOR i = 0 TO maxval * fgmt
    c = cnt(i)
    cnt(i) = tot
    tot = tot + c
NEXT i
DIM outt(-1 TO items - 1) AS SINGLE
'PRINT
'PRINT "Partial sort";
FOR i = 0 TO items - 1
    outt(cnt(k(i).b)) = k(i).a
    cnt(k(i).b) = cnt(k(i).b) + 1
NEXT i
FOR i = 0 TO items - 1
    '   PRINT STR$(outt(I));
    PSET (i + items * 1.1, (maxval - outt(i)) * 15), 15
NEXT i
PRINT
'now insertion sort 'guided by Wikipedia

FOR n = 0 TO items - 1
    vals = outt(n)
    j = n - 1
    comp = 0
    DO
        IF outt(j) > vals THEN
            outt(j + 1) = outt(j)
            j = j - 1
            IF j < 0 THEN comp = 1
        ELSE
            comp = 1
        END IF
    LOOP UNTIL comp
    outt(j + 1) = vals
NEXT n

FOR i = 0 TO items - 1
    PSET (i + items * 2.2, (maxval - outt(i)) * 15), 15
NEXT i

shunt sort uses a modified counting sort as a presort to get the data into a order that the later sorting algorithm can handle faster.
« Last Edit: October 21, 2012, 01:33:08 PM by DarthWho »
Rassilon: My lord Doctor; My lord Master; My lord DarthWho
The Doctor and the master at the same time :WHAT!?!?!

FastMath 1.1.0 released: http://dl.dropbox.com/u/12359848/fastmath.h

23452

  • Jr. Member
  • **
  • Posts: 72
    • Email
Re: rearranging arrays
« Reply #6 on: October 21, 2012, 01:40:13 PM »
I will go with the comb one.
It is a little slower then I was hoping, but I need to swap 4 arrays based on the same results, and that will be easy with comb.
As for bubble why did you tell me to eat a cookie, I had time to bake them. 

DarthWho

  • Hero Member
  • *****
  • Posts: 3853
  • Timelord of the Sith
Re: rearranging arrays
« Reply #7 on: October 21, 2012, 02:14:44 PM »
hey SMcNeill I modded the code you posted to handle longs instead of _integer64s (because of certain limitations of counting sort) and set the limit to 10,000,000  and counting sort sorted everything in 1.661 seconds  ;D
combsort pulled it off in 27.418 seconds and I didn't even try bubblesort
Code: [Select]
limit = 10000000

DIM k(limit) AS LONG
RANDOMIZE TIMER
PRINT "Initializing Data"
FOR i = 0 TO limit
    k(i) = RND(1) * 32767
NEXT


t# = TIMER(0.001)
items = limit
'DIM k(items - 1) AS INTEGER
'fill k
'for simplicity's sake 10 is max 0 is min provides guarantee of duplication
'RANDOMIZE TIMER
maxval = 32767
'PRINT "unsorted";
''FOR i = 0 TO items - 1
''k(i) = INT((maxval + 1) * RND)
''PRINT STR$(k(i));
''NEXT i
DIM cnt(0 TO maxval)
FOR i = 0 TO items - 1
    cnt(k(i)) = cnt(k(i)) + 1
NEXT i
FOR i = 0 TO maxval
    c = cnt(i)
    cnt(i) = tot
    tot = tot + c
NEXT i
DIM outt(items - 1)
'PRINT
'PRINT "sorted";
FOR i = 0 TO items - 1
    outt(cnt(k(i))) = k(i)
    cnt(k(i)) = cnt(k(i)) + 1
NEXT i
FOR i = 0 TO items - 1
    k(i) = outt(i) 'PRINT STR$(outt(i));
NEXT i
'

'PRINT "Bubble Sorting Data": bubblesort x()
'PRINT "Comb Sorting Data" : combsort x()

t1# = TIMER(0.001)
PRINT USING "Data Sorted in ##,###.##### seconds."; t1# - t#
SLEEP
Rassilon: My lord Doctor; My lord Master; My lord DarthWho
The Doctor and the master at the same time :WHAT!?!?!

FastMath 1.1.0 released: http://dl.dropbox.com/u/12359848/fastmath.h

23452

  • Jr. Member
  • **
  • Posts: 72
    • Email
Re: rearranging arrays
« Reply #8 on: October 21, 2012, 02:40:42 PM »
O_O that is much faster, but it confuses me a little bit. Is it possible to swap 4 arrays using that.

d(0) = 9
d(1) = 3
c(0)= 4
c(1) = 10
needs to become
d(0) = 3
d(1) = 9
c(0) = 10
c(1) = 4

and so on with the set of values the same, but the number they are stored in changing

Gorlock

  • Sr. Member
  • ****
  • Posts: 337
    • Email
Re: rearranging arrays
« Reply #9 on: October 21, 2012, 03:03:09 PM »
Yes probably, do you mean like every element in each row is swapped with its partner? If so you could just use:

Code: [Select]
REDIM a$(1, 2)

c(0) = 4
c(1) = 10
a(0, 0) = 4
a(0, 1) = 10

d(0) = 9
d(1) = 3
a(1, 0) = 9
a(1, 1) = 3

FOR x = 0 TO 1
    SWAP a(x, 0), a(x, 1)
NEXT x

FOR pa = 0 TO 1

    FOR pb = 0 TO 1
        PRINT a(pa, pb)
NEXT pb, pa

and if you really want it to print backwards like that you can always change the direction it prints:

Code: [Select]
REDIM a$(1, 2)

c(0) = 4
c(1) = 10
a(0, 0) = 4
a(0, 1) = 10

d(0) = 9
d(1) = 3
a(1, 0) = 9
a(1, 1) = 3

FOR x = 0 TO 1
    SWAP a(x, 0), a(x, 1)
NEXT x

FOR pa = 1 TO 0 STEP -1

    FOR pb = 0 TO 1
        PRINT a(pa, pb)
NEXT pb, pa

Clippy

  • Hero Member
  • *****
  • Posts: 16431
  • I LOVE π = 4 * ATN(1)    Use the QB64 WIKI >>>
    • Pete's Qbasic Site
    • Email
Re: rearranging arrays
« Reply #10 on: October 21, 2012, 03:11:34 PM »
QuickSort:

Code: [Select]
OPTION BASE 1
DIM Array2(10000) AS SINGLE
DIM swap2 AS LONG
SCREEN 12
arraysize% = UBOUND(Array2)
RANDOMIZE TIMER
FOR i = 1 TO 10000
  Array2(i) = RND * 10000
NEXT
LOCATE 10, 10: PRINT Array2(1); Array2(5000); Array2(10000); arraysize%
COLOR 13: LOCATE 26, 4: PRINT "Press any key to Quicksort 10000 index array!"
K$ = INPUT$(1)


start = TIMER(.001)
swap2 = 0
CALL QuickSort(1, arraysize%, Array2(), swap2)
finish = TIMER(.001)
elapsed = finish - start
OK% = 1
FOR i = 1 TO arraysize% - 1
  IF Array2(i) > Array2(i + 1) THEN OK% = 0: EXIT FOR
NEXT i
IF OK% = 1 THEN
  report$ = "  No errors!,"
ELSE: report$ = "SORT FAILED!,"
END IF
LOCATE 15, 10: PRINT "ET:"; elapsed; report$; Array2(1); Array2(5000); Array2(10000); "Swaps:"; swap2

SUB QuickSort (start AS INTEGER, finish AS INTEGER, a() AS SINGLE, swap2 AS LONG)
DIM Hi AS INTEGER, Lo AS INTEGER, Middle AS SINGLE
Hi = finish: Lo = start '1 10000
Middle = a((Lo + Hi) \ 2) 'find middle of array
DO
  DO WHILE a(Lo) < Middle: Lo = Lo + 1: LOOP '5000
  DO WHILE a(Hi) > Middle: Hi = Hi - 1: LOOP '5000
  IF Lo <= Hi THEN
    SWAP a(Lo), a(Hi)
    swap2 = swap2 + 1 'for demo only
    Lo = Lo + 1: Hi = Hi - 1
  END IF
LOOP UNTIL Lo > Hi

IF Hi > start THEN CALL QuickSort(start, Hi, a(), swap2)
IF Lo < finish THEN CALL QuickSort(Lo, finish, a(), swap2)

END SUB

swap2 is for demo only.
« Last Edit: October 21, 2012, 03:43:46 PM by Clippy »
QB64 WIKI: Main Page
Download Q-Basics Code Demo: Q-Basics.zip
Download QB64 BAT, IconAdder and VBS shortcuts: QB64BAT.zip
Download QB64 DLL files in a ZIP: Program64.zip

SMcNeill

  • Hero Member
  • *****
  • Posts: 2414
    • Email
Re: rearranging arrays
« Reply #11 on: October 21, 2012, 04:01:47 PM »
Quote from: DarthWho on October 21, 2012, 02:14:44 PM
hey SMcNeill I modded the code you posted to handle longs instead of _integer64s (because of certain limitations of counting sort) and set the limit to 10,000,000  and counting sort sorted everything in 1.661 seconds  ;D
combsort pulled it off in 27.418 seconds and I didn't even try bubblesort

Making a few minor adjustments, we can get the combsort routine down to about 10 seconds or so:
Code: [Select]
CONST limit = 10000000

DIM x(limit) AS LONG
RANDOMIZE TIMER
PRINT "Initializing Data"
FOR i = 0 TO limit
    x(i) = RND(1) * 32767
NEXT

PRINT "Comb Sorting Data"
t# = TIMER(0.001): combsort x(): t1# = TIMER(0.001)
PRINT USING "Data Sorted in ##,###.##### seconds."; t1# - t#
END


SUB combsort (array() AS LONG)
DIM i AS LONG, l AS LONG, gap AS LONG, x as LONG
gap = limit
DO
    gap = INT(gap / 1.247330950103979)
    IF gap < 1 THEN gap = 1
    i = 0
    DO
        x = i + gap
        IF array(i) > array(x) THEN SWAP array(i), array(x)
        i = i + 1
    LOOP UNTIL x >= limit
LOOP UNTIL gap = 1
END SUB

Not as good as the 1.6 second counting sort time, but still not something to sneeze at for 10 million sorts!  :)

We can actually cut a good chunk off  the time of our comb sort, if we'd exit out when the gap is <= 10 instead of running all the way to 1, and then finishing up with an insertion sort routine.  Once the gap gets down to 10, we're almost to the point of doing a bubble sort once again for the last several passes (and you can see how inefficient that is overall), so if we'd swap over to an insertion sort to finish up things would go faster.

It's more coding and a little more work, and I thought I'd keep the examples simple, but you can optimize and get better performance if you want to.  (I'd actually considered using the combsort-to-insertionsort method on my QBDbase routines, but they seem efficient enough to me for now.  They're to the point where we sort close to a million records in ~ 3 seconds, and that seems like it's good enough, honestly.  I really don't want to add a couple hundred/thousand more lines to code just to shave off 1 or 2 seconds of sort time which honestly shouldn't affect a lot of people.  Just how many people are out there using QB64 who need to sort a million records in less than a second?!  ;)

Thing is, there's a lot of different sorting methods out there.  You just need to find one that works simple enough for you to code, and fast enough for your purposes.  Some work better with numbers, some with text, and a few just seem amazing for *this* code, but  sucky for *that* code, and no one really seems to know WHY it works as it does...   :)

I like the comb sort just for the simplicity.  It's not much more code than a bubble sort, but I'll be darned if it isn't a TON faster.  Simplicity, and acceptable performance all in one.  Hard to beat overall really. :D
http://bit.ly/TextImage -- Library of QB64 code to manipulate text and images, as a BM library.
http://bit.ly/Color32 -- A set of color CONST for use in 32 bit mode, as a BI library.

http://bit.ly/DataToDrive - A set of routines to quickly and easily get data to and from the disk.  BI and BM files

23452

  • Jr. Member
  • **
  • Posts: 72
    • Email
Re: rearranging arrays
« Reply #12 on: October 21, 2012, 04:20:11 PM »
Okay maybe it would be better if say the entire problem.
I am using this in a voxel engine, so it needs to be fast.
o is a voxel and has a x, y, z, and a color value. x(o), y(o), z(o), c(o)
They are only one element arrays because I am using them like a math function.
I use x(o), y(o) and z(o) to calculate where they will be drawn on the screen. xf(o) and yf(o)
The problem is that it is drawing one object over the other based on the objects number.
I can calculate the the distance from the eye( this works like a real eye, so the eye and the screen are not at the same place) by mixing the distance formula  and Pythagorean theorem, and I need it to draw from the greatest distance to smallest. 
 

DarthWho

  • Hero Member
  • *****
  • Posts: 3853
  • Timelord of the Sith
Re: rearranging arrays
« Reply #13 on: October 21, 2012, 05:08:03 PM »
yeah I like Counting sort for it's insane speed levels but I was not happy about it's inability to deal with decimal numbers... so I created shunt sort to solve that problem; a bit slower than counting sort but it can handle decimal numbers. unfortunately it cannot handle the really massive sizes... (my machine runs out of memory at an array of 71360 elements... I am trying to work out how to solve the memory problems)
Rassilon: My lord Doctor; My lord Master; My lord DarthWho
The Doctor and the master at the same time :WHAT!?!?!

FastMath 1.1.0 released: http://dl.dropbox.com/u/12359848/fastmath.h

LeChuck

  • Hero Member
  • *****
  • Posts: 895
  • 18 * 37
Re: rearranging arrays
« Reply #14 on: October 24, 2012, 04:04:58 AM »
The trick is not to sort.

My sort does 10000000 items in under a second easily on my i7 and about 5 seconds on my slow-as-hell netbook. Unoptimized in it's current state, out of time atm.

Code: [Select]
'LeChuck's sort (unoptimized)

RANDOMIZE TIMER
_DEFINE A-Z AS _INTEGER64

ArraySize = 10000000
DIM Array(ArraySize)
DIM Sorted(ArraySize)
DIM Unsorted(ArraySize)

FOR j = 1 TO ArraySize 'generate random unsorted array
    Unsorted(j) = INT(RND * ArraySize)
NEXT j

t! = TIMER
FOR j = 1 TO ArraySize
    Array(Unsorted(j)) = Array(Unsorted(j)) + 1
NEXT j
FOR j = 1 TO ArraySize
    FOR k = 1 TO Array(j)
        s = s + 1
        Sorted(s) = j
        'PRINT Sorted(s) 'uncheck if you want to see it's sorted as it should be
    NEXT k
NEXT j
PRINT ArraySize; "items sorted in:"; TIMER - t!; "seconds."
Two or more, use a FOR!

  • Print