Quicksort

What is it?

Quicksort is an algorithm used for sorting lists. It uses the Divide and Conquer algorithm approach in combination with recursion.

To understand quicksort, I recommend watching this short Youtube video and reading the quicksort geeksforgeeks page.

Best Solution

The best quicksort kdb solution is that documented by Anna on her blog Me, q and kdb+:

q:{$[2>distinct x;x;raze q each x where each not scan x < rand x]}

Let's make that a bit easier to read:

q:{

$[2>distinct x;

  x;

  raze .z.s each x where each not scan x < rand x

]

 }

In recursion, we always want to have a base condition. In this case, the base condition is: if there is only one (distinct) value, return that value.

Otherwise, take a random pivot value from the list:

rand x

Standard Solution

The standard solution as demonstrated in the two links above uses recursion to partition the data and then re-order each set of partitioned data based on whether the value is greater or less than the pivot value.

The standard solution in kdb might look something like:

quicksort:{[array;low;high]

if[low < high;

  params:(array;high;-1;0);

  res:((count array)trav/params);

  piv:res 2;

  array:res 0;

  array:.z.s[array;low;piv - 1];

  array:.z.s[array;piv+1;high];

];

array

 };

trav:{

arr:x 0;piv:x 1;i:x 2;j:x 3;

if[arr[j] <= arr[piv];

  i+:1;

  from:arr[i];to:arr[j];

  arr:@[arr;i,j;:;to,from];

];

j+:1;

(arr;piv;i;j)

 };

quicksort[10 80 30 90 40 50 70;0;-1+count array]