Quick sort

From Ninerpedia
Jump to navigation Jump to search

Sorting is often very useful. Here is a fast sorting routine in BASIC.

QUICK SORT

Sorting data is a frequent task for many programs, and it seems reasonable to use the fastest sorting method available.

This sorting routine is very fast.

The variables used are: A,B,C,D,E, F(), A$(), B$

To use the sort, your program must contain the initialisation lines (100-150) at the beginning. You should not use the above variables in the main program, but if necessary you can change the variable names in this routine to avoid conflict.

The initialisation here is for 200 items. If you wish to sort a different number of items, set C to the number of items to be sorted (line 130) and DIMension A$ in line 100 to the number of items plus one. Then in line 150 set A$(Number of items plus one) to CHR$(124) (looks like | ) (press FCTN and A keys together).

Your program may enter the routine with GOTO (EXIT with GOTO) or with GOSUB (EXIT with RETURN).

The items to be sorted are to be placed in the array A$(), and when the routine is finished, the items will still be in the array, but in ascending order,depending on the ASCII codes of their letters. Note that A$(0) should NOT be used and left empty, it is used as a flag:

Sorting order: eg AA after A, B after AZZZ and so on.

This routine will sort up to 1000 items. After that, you will need to DIMension the F array- to F(11) for 2000 items, F(12) for 4000 items and so on. The default if you do not use DIM is (10).


Initialisation:

        100 DIM A$(201)
        110 A=1
        120 B=1
        130 C=200
        140 A$(0)=" "
        150 A$(201)=CHR$(124)
                        

{ program }

                      
       2000 IF C-B<10 THEN 2320
       2010 D=B
       2020 E=C
       2030 B$=A$(B)
       2040 IF B$>=A$(E)THEN 2070
       2050 E=E-1
       2060 GOTO 2040
       2070 IF E>D THEN 2100
       2080 A$(D)=B$
       2090 GOTO 2190
       2100 A$(D)=A$(E)
       2110 D=D+1
       2120 IF A$(D)<B$ THEN 2110
       2130 IF E>D THEN 2170
       2140 A$(E)=B$
       2150 D=E
       2160 GOTO 2190
       2170 A$(E)=A$(D)
       2180 GOTO 2050
       2190 IF C-D<D-B THEN 2260
       2200 F(A)=C
       2210 A=A+1
       2220 F(A)=D+1
       2230 A=A+1
       2240 C=D-1
       2250 GOTO 2000
       2260 F(A)=D-1
       2270 A=A+1
       2280 F(A)=B
       2290 A=A+1
       2300 B=D+1
       2310 GOTO 2000
       2320 E=B
       2330 E=E+1
       2340 IF E>C THEN 2430
       2350 B$=A$(E)
       2360 D=E-1
       2370 IF A$(D)<=B$ THEN 2410
       2380 A$(D+1)=A$(D)
       2390 D=D-1
       2400 GOTO 2370
       2410 A$(D+1)=B$
       2420 GOTO 2330
       2430 IF A=1 THEN 2490
       2440 A=A-1
       2450 B=F(A)
       2460 A=A-1
       2470 C=F(A)
       2480 GOTO 2000
       2490 RETURN