# Quick sort

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   `
```