Quick Sort - GameCreators Forum

Author

Message

Codger

23

Years of Service

User Offline

Joined: 23rd Nov 2002

Location:

Posted: 1st Oct 2003 17:53

Link

Hi
Does anyone have a QuickSort function coded that they would be willing to post?

If not I will code and post one shortly

Thanks

System
PIII 650 MZ H.P. Pavillion
394 Mem GeForce 4 400MX

Back to top

Profile PM Email

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 1st Oct 2003 20:09

Link

There's one on DBDN but I guess that's not really available - I couldn't post a copy of it here unless the coder (GuyS) agreed.

However, I have a plugin that's freely available from my site that allows arrays and ranges in arrays to be sorted fast and safely.

Still, it would be a good addition to Codebase as an example to show how it's done

Back to top

Profile PM Email Website

Codger

23

Years of Service

User Offline

Joined: 23rd Nov 2002

Location:

Posted: 1st Oct 2003 21:11

Link

I made my own it includes a graphic example. Try it out and let me know if improvements can be made. I will then add to code base

set window on
SET DISPLAY MODE 1024,768,32
   set text font "verdana" rem "WESTMINSTER"
   Set text size 16
   SET TEXT OPAQUE
ink RGB(255,255,255),RGB(1,1,1)
color backdrop RGB(0,0,120)

sync off
sync rate 0

global N as integer
global L as  Integer

cls
randomize timer()
set cursor 10,10
input "Enter Array Size to Sort : ", N
dim A(N) as integer

for L = 1 to N
   A(L) = rnd(500)
next L

StartTime = timer()
set cursor 10,30
print "Sorting ",N," numbers..."
sync on
sync rate 0

QuickSort(1,N)

sync off

EndTime = Timer()-StartTime

Set Cursor 10,50
Print "Time Taken ",Endtime

wait key

Function QuickSort(L,R)
   I as integer
   J as integer
   X as integer
   W as integer
rem remark out or delete  the next line to disable graphics
rem 500 items take approx 15 seconds with graphic .004 seconds without
     DrawArray()

I = L
      J = R
      X = A((L+R)/2)
      repeat
         while A(I) < X
            inc I
         endwhile
         while X < A(J)
            dec J
         endwhile
         if I <= J
            W = A(I)
            A(I) = A(J)
            A(J) = W
            I = I + 1
            J = J - 1
         endif
      until I >= J
      if L < J then QuickSort(L,J)
      if I < R then QuickSort(I,R)
EndFunction

Function DrawArray()
  cls
  for i = 1 to N
     line 1,100+i,1+A(i),100+i
  next i
  sync
endfunction

+ Code Snippet

set window on
SET DISPLAY MODE 1024,768,32
   set text font "verdana" rem "WESTMINSTER"
   Set text size 16
   SET TEXT OPAQUE
ink RGB(255,255,255),RGB(1,1,1)
color backdrop RGB(0,0,120)

sync off
sync rate 0

global N as integer
global L as  Integer


cls
randomize timer()
set cursor 10,10
input "Enter Array Size to Sort : ", N
dim A(N) as integer

for L = 1 to N
   A(L) = rnd(500)
next L

StartTime = timer()
set cursor 10,30
print "Sorting ",N," numbers..."
sync on
sync rate 0

QuickSort(1,N)

sync off

EndTime = Timer()-StartTime

Set Cursor 10,50
Print "Time Taken ",Endtime

wait key


Function QuickSort(L,R)
   I as integer
   J as integer
   X as integer
   W as integer
rem remark out or delete  the next line to disable graphics
rem 500 items take approx 15 seconds with graphic .004 seconds without
     DrawArray()

      I = L
      J = R
      X = A((L+R)/2)
      repeat
         while A(I) < X
            inc I
         endwhile
         while X < A(J)
            dec J
         endwhile
         if I <= J
            W = A(I)
            A(I) = A(J)
            A(J) = W
            I = I + 1
            J = J - 1
         endif
      until I >= J
      if L < J then QuickSort(L,J)
      if I < R then QuickSort(I,R)
EndFunction


Function DrawArray()
  cls
  for i = 1 to N
     line 1,100+i,1+A(i),100+i
  next i
  sync
endfunction

System
PIII 650 MZ H.P. Pavillion
394 Mem GeForce 4 400MX

Back to top

Profile PM Email

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 1st Oct 2003 21:30

Link

Good stuff

Just drop the attached function into your code in place of your DrawArray function and you'll see a massive speedup when drawing.

+ Code Snippet

Function DrawArray()
  box 0,100,1000,100+N,0,0,0,0
  lock pixels
  for i = 1 to N
     line 1,100+i,1+A(i),100+i
  next i
  unlock pixels
  sync
endfunction

Back to top

Profile PM Email Website

Codger

23

Years of Service

User Offline

Joined: 23rd Nov 2002

Location:

Posted: 1st Oct 2003 22:31 Edited at: 1st Oct 2003 22:34

Link

IanM
I had heard about the lock Pixels command but when I tried it the program took exactly the same amount of time, around 15 seconds for an array of 500.

Did you get an improvement in speed?

System
PIII 650 MZ H.P. Pavillion
394 Mem GeForce 4 400MX

Back to top

Profile PM Email

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 1st Oct 2003 23:13 Edited at: 1st Oct 2003 23:13

Link

Yep. My laptop is relatively slow ... I got an increase in speed from 18.6 seconds down to 10.4 seconds.

Perhaps the speed increase is due to the age of my laptop (over 2 years old now) because when I ran the programs on my desktop machine I got no difference in speed either ... interestingly, it only ran as fast as my laptop!

The LOCK PIXELS command can speed up POINT, DOT, LINE, CIRCLE and ELLIPSE and drawing/reading directly to the display with the memory access commands.

Other draw commands are not sped up (or could even cause a program crash) because they are hardware accelerated.

Back to top

Profile PM Email Website

Codger

23

Years of Service

User Offline

Joined: 23rd Nov 2002

Location:

Posted: 2nd Oct 2003 00:10 Edited at: 2nd Oct 2003 00:12

Link

Modified the Graphics Portion to only redraw the swapped data

set window on
SET DISPLAY MODE 1024,768,32
   set text font "verdana" rem "WESTMINSTER"
   Set text size 16
   SET TEXT OPAQUE
ink RGB(255,255,255),RGB(1,1,1)
color backdrop RGB(0,0,120)

sync off
sync rate 0

global N as integer
global L as  Integer

cls
randomize timer()
set cursor 10,10
input "Enter Array Size to Sort : ", N
dim A(N) as integer

for L = 1 to N
   A(L) = rnd(1024)
next L

set cursor 10,30
print "Sorting ",N," numbers..."
sync on
sync rate 0

DrawArray()

StartTime = timer()

QuickSort(1,N)

sync off

EndTime = Timer()-StartTime
DrawArray()
Set Cursor 10,50
Print "Time Taken ",Endtime, " Miliseconds"
wait key

Function QuickSort(L,R)
   I as integer
   J as integer
   X as integer
   W as integer

I = L
      J = R
      X = A((L+R)/2)
      repeat
         while A(I) < X
            inc I
         endwhile
         while X < A(J)
            dec J
         endwhile
         if I <= J
            W = A(I)
            A(I) = A(J)
            A(J) = W

rem remark out or delete  the next 2 line to disable graphics
rem 500 items take approx 5 seconds with graphic 1 or 2 miliseconds without
 rem           DrawLine(I)
 rem           Drawline(J)

I = I + 1
            J = J - 1

endif
      until I >= J
      if L < J then QuickSort(L,J)
      if I < R then QuickSort(I,R)
EndFunction

Function DrawLine(i)
rem  lock pixels
      ink Rgb(125,0,0),Rgb(0,0,0)
     line 1,100+i,A(i),100+i
      ink Rgb(0,0,0),Rgb(255,255,255)
     line A(i),100+i,1024,100+i
rem      unlock pixels
     sync
endfunction

Function DrawArray()
  box 0,100,1000,100+N,0,0,0,0
  for i = 1 to N
     DrawLine(i)
  next i
  sync
endfunction

+ Code Snippet

set window on
SET DISPLAY MODE 1024,768,32
   set text font "verdana" rem "WESTMINSTER"
   Set text size 16
   SET TEXT OPAQUE
ink RGB(255,255,255),RGB(1,1,1)
color backdrop RGB(0,0,120)

sync off
sync rate 0

global N as integer
global L as  Integer


cls
randomize timer()
set cursor 10,10
input "Enter Array Size to Sort : ", N
dim A(N) as integer

for L = 1 to N
   A(L) = rnd(1024)
next L


set cursor 10,30
print "Sorting ",N," numbers..."
sync on
sync rate 0

DrawArray()

StartTime = timer()

QuickSort(1,N)

sync off

EndTime = Timer()-StartTime
DrawArray()
Set Cursor 10,50
Print "Time Taken ",Endtime, " Miliseconds"
wait key

Function QuickSort(L,R)
   I as integer
   J as integer
   X as integer
   W as integer

      I = L
      J = R
      X = A((L+R)/2)
      repeat
         while A(I) < X
            inc I
         endwhile
         while X < A(J)
            dec J
         endwhile
         if I <= J
            W = A(I)
            A(I) = A(J)
            A(J) = W

rem remark out or delete  the next 2 line to disable graphics
rem 500 items take approx 5 seconds with graphic 1 or 2 miliseconds without
 rem           DrawLine(I)
 rem           Drawline(J)

            I = I + 1
            J = J - 1

         endif
      until I >= J
      if L < J then QuickSort(L,J)
      if I < R then QuickSort(I,R)
EndFunction

Function DrawLine(i)
rem  lock pixels
      ink Rgb(125,0,0),Rgb(0,0,0)
     line 1,100+i,A(i),100+i
      ink Rgb(0,0,0),Rgb(255,255,255)
     line A(i),100+i,1024,100+i
rem      unlock pixels
     sync
endfunction


Function DrawArray()
  box 0,100,1000,100+N,0,0,0,0
  for i = 1 to N
     DrawLine(i)
  next i
  sync
endfunction

Run Time reduced to 30% remove rem's to see sort take place

System
PIII 650 MZ H.P. Pavillion
394 Mem GeForce 4 400MX

Back to top

Profile PM Email

Sorry your browser is not supported!

DarkBASIC Professional Discussion / Quick Sort