Quicksort is a classic sorting algorithm invented by C.A.R. Hoare in 1961 [0, 1]. It has been known for some time that quicksort has a terse rendition in APL [2]. To get right to it, here is the code:
Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}
The “pivot” ⍵⌷⍨?≢⍵ is randomly chosen. ((∇<S)⍪=S⍪(∇>S)) is a fork, selecting the parts of ⍵ which are less than the pivot, equal to the pivot, and greater than the pivot. The function is recursively applied to the first and the last of these three parts.
⎕io←0 ⋄ ⎕rl←7*5
⎕←x←?13⍴20
3 2 19 16 11 4 18 17 9 17 7 3 1
Q x
1 2 3 3 4 7 9 11 16 17 17 18 19
The variant Q1 obtains by enclosing each of the three parts. Its result exhibits an interesting structure. The middle item of each triplet is the value of the pivot at each recursion. Since the pivot is randomly chosen, the result of Q1 can be different on the same argument, as illustrated below:
Q1←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((⊂∘∇<S)⍪(⊂=S)⍪(⊂∘∇>S))⍵⌷⍨?≢⍵}
Q1 x
┌──────┬───┬────────────────────────────────────┐
│┌─┬─┬┐│3 3│┌─┬─┬──────────────────────────────┐│
││1│2│││ ││4│7│┌┬─┬─────────────────────────┐││
│└─┴─┴┘│ ││ │ │││9│┌──┬──┬─────────────────┐│││
│ │ ││ │ │││ ││11│16│┌─────────┬──┬──┐││││
│ │ ││ │ │││ ││ │ ││┌┬─────┬┐│18│19│││││
│ │ ││ │ │││ ││ │ ││││17 17│││ │ │││││
│ │ ││ │ │││ ││ │ ││└┴─────┴┘│ │ │││││
│ │ ││ │ │││ ││ │ │└─────────┴──┴──┘││││
│ │ ││ │ │││ │└──┴──┴─────────────────┘│││
│ │ ││ │ │└┴─┴─────────────────────────┘││
│ │ │└─┴─┴──────────────────────────────┘│
└──────┴───┴────────────────────────────────────┘
Q1 x
┌───────────────────────┬─┬─────────────────────────┐
│┌──────────────────┬─┬┐│9│┌──┬──┬─────────────────┐│
││┌┬─┬─────────────┐│7│││ ││11│16│┌───────────┬──┬┐││
││││1│┌┬─┬────────┐││ │││ ││ │ ││┌┬─────┬──┐│19││││
││││ │││2│┌┬───┬─┐│││ │││ ││ │ ││││17 17│18││ ││││
││││ │││ │││3 3│4││││ │││ ││ │ ││└┴─────┴──┘│ ││││
││││ │││ │└┴───┴─┘│││ │││ ││ │ │└───────────┴──┴┘││
││││ │└┴─┴────────┘││ │││ │└──┴──┴─────────────────┘│
││└┴─┴─────────────┘│ │││ │ │
│└──────────────────┴─┴┘│ │ │
└───────────────────────┴─┴─────────────────────────┘
The enlist of the result of Q1 x is the same as Q x, the sort of x:
∊ Q1 x
1 2 3 3 4 7 9 11 16 17 17 18 19
Q x
1 2 3 3 4 7 9 11 16 17 17 18 19
This note is meant to explore the workings of a classical algorithm. To actually sort data in Dyalog, it is more convenient and more efficient to use {⍵[⍋⍵]}. Earlier versions of this text appeared in [3, 4].
References
- Hoare, C.A.R, Algorithm 63: Partition, Communications of the ACM, Volume 4, Number 7, 1961-07.
- Hoare, C.A.R, Algorithm 64: Quicksort, Communications of the ACM, Volume 4, Number 7, 1961-07.
- Hui, Roger K.W., and Kenneth E. Iverson, J Introduction and Dictionary, 1991-2014;
if. entry.
- Hui, Roger K.W., Quicksort, J Wiki Essay, 2005-09-28.
- Hui, Roger K.W. Sixteen APL Amuse-Bouches, 2014-11-02.
Follow