7. Quicksort

Q←{1≥≢⍵:⍵ ⋄ (∇ ⍵⌿⍨0>s),(⍵⌿⍨0=s),∇ ⍵⌿⍨0<s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵}

Quicksort [27, 28, 29]

The operand ⍺⍺ is required to be a scalar function which returns a number less than 0, equal to 0, or greater than 0, according to whether ⍺ is less than, equal to, or greater than ⍵ . In Q , the phrase s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵ compares each cell of ⍵ against a randomly-chosen “pivot” ⍵⌷⍨?≢⍵ ; the function then applies recursively to the elements of ⍵ which are less than the pivot (0>s) and those which are greater than the pivot (0<s) .

Example with numbers:

   ⎕←x←?13⍴20
2 2 7 10 10 11 3 10 14 5 9 1 16

   -Q x
1 2 2 3 5 7 9 10 10 10 11 14 16

Example with strings:

   a←'Fi' 'Jay' 'John' 'Morten' 'Roger' 'JD' 'Jd' 'Anna' 'Scott' 'Zeus'

   strcmp←{⍺≡⍵:0 ⋄ -/⍋↑⍺ ⍵}

   strcmp¨ Q a
┌────┬──┬──┬───┬──┬────┬──────┬─────┬─────┬────┐
│Anna│Fi│JD│Jay│Jd│John│Morten│Roger│Scott│Zeus│
└────┴──┴──┴───┴──┴────┴──────┴─────┴─────┴────┘

Triplets

The variant Q1 encloses each of the three parts, resulting in an array with 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 results of Q1 can be different on the same argument.

   Q1←{1≥≢⍵:⍵ ⋄ (⊂∇ ⍵⌿⍨0>s),(⊂⍵⌿⍨0=s),⊂∇ ⍵⌿⍨0<s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵}

   -Q1 x
┌─────────┬─┬────────────────────────────────┐
│┌─┬───┬─┐│5│┌┬─┬───────────────────────────┐│
││1│2 2│3││ │││7│┌─┬────────┬──────────────┐││
│└─┴───┴─┘│ │││ ││9│10 10 10│┌┬──┬────────┐│││
│         │ │││ ││ │        │││11│┌┬──┬──┐││││
│         │ │││ ││ │        │││  │││14│16│││││
│         │ │││ ││ │        │││  │└┴──┴──┘││││
│         │ │││ ││ │        │└┴──┴────────┘│││
│         │ │││ │└─┴────────┴──────────────┘││
│         │ │└┴─┴───────────────────────────┘│
└─────────┴─┴────────────────────────────────┘
   -Q1 x
┌────────────────────────────────┬──┬────────┐
│┌────────────────────┬────────┬┐│11│┌┬──┬──┐│
││┌──────────────┬─┬─┐│10 10 10│││  │││14│16││
│││┌─┬───┬──────┐│7│9││        │││  │└┴──┴──┘│
││││1│2 2│┌─┬─┬┐││ │ ││        │││  │        │
││││ │   ││3│5││││ │ ││        │││  │        │
││││ │   │└─┴─┴┘││ │ ││        │││  │        │
│││└─┴───┴──────┘│ │ ││        │││  │        │
││└──────────────┴─┴─┘│        │││  │        │
│└────────────────────┴────────┴┘│  │        │
└────────────────────────────────┴──┴────────┘
   ∊ - Q1 x
1 2 2 3 5 7 9 10 10 10 11 14 16

Order Statistic [30, 31]

S1←{⍵⌷⍨⍺⌷⍋⍵} computes the order statistic: 0 S1 ⍵ is the smallest cell of ⍵ and (¯1+≢⍵)S1 ⍵ is the biggest (and (2÷⍨¯1+≢⍵)S1 ⍵ is the median if ≢⍵ is odd).

   x←?(1+1e6)⍴2e9

   (⌊/x), 0 S1 x
87 87
   (⌈/x), (¯1+≢x)S1 x
1999998274 1999998274

   ⎕←m←(2÷⍨¯1+≢x)S1 x
999669657
   +/m<x
500000
   +/m>x
500000

A linear algorithm for the order statistic derives from the Quicksort strategy. The argument is partitioned into groups of cells less than a randomly-chosen pivot, equal to the pivot, and greater than the pivot. Requirements on the operand ⍺⍺ are as above.

S←{
  s←⍵ ⍺⍺ p←⍵⌷⍨?≢⍵
  ⍺<  +/b←0>s:⍺ ∇ b⌿⍵
  ⍺<m←+/b←0≥s:p
  (⍺-m) ∇ (~b)⌿⍵
}

   0 -S x
87
   (¯1+≢x) -S x
1999998274
   (2÷⍨¯1+≢x) -S x
999669657

S1 is less efficient than S because S1 sorts the entire argument, which S does not do. A version Sn for numeric vectors with a “hardwired” comparison is even faster:

Sn←{
  p←⍵⌷⍨?≢⍵
  ⍺<  +/b←⍵<p:⍺ ∇ b⌿⍵
  ⍺<m←+/b←⍵≤p:p
  (⍺-m) ∇ (~b)⌿⍵
}

   i←?≢x

   cmpx 'i S1 x' 'i -S x' 'i Sn x'
  i S1 x → 7.14E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  i -S x → 1.03E¯2 | -86% ⎕⎕⎕⎕
  i Sn x → 8.72E¯3 | -88% ⎕⎕⎕⎕