Quicksort in eight lines

[Richard Russell]

Inspired by a YouTube video showing a Quicksort done in 5 lines of Haskell, I wrote this version in 8 lines of BBC BASIC. It's not the fastest or most memory efficient code - an in-place Quicksort such as at Rosetta Code will outperform it in both respects - but it's the shortest and most 'obvious' implementation I know. N% is the total number of elements to be sorted in the (zero-based) array.

Code: Select all

      DEF PROCqsort(x(), N%) : IF N% < 2 ENDPROC
      LOCAL I%, J%, K%, l(), r() : DIM l(N%-2), r(N%-2)
      FOR I% = 1 TO N%-1
        IF x(I%) < x(0) l(J%) = x(I%) : J% += 1 ELSE r(K%) = x(I%) : K% += 1
      NEXT : PROCqsort(l(), J%) : PROCqsort(r(), K%) : x(J%) = x(0)
      FOR I% = 0 TO N%-1
        IF I% < J% x(I%) = l(I%) ELSE IF I% > J% x(I%) = r(I%-J%-1)
      NEXT : ENDPROC