Lesson 17 · 17 of 20
Quicksort and binary search · Pascal
Write quicksort and binary search in Pascal with open arrays and recursion, and see why searching a sorted list is so fast.
Quicksort sorts by picking a pivot and moving smaller values to its left and larger ones to its right; then it does the same to each side. This version (the Lomuto partition) uses the last element, a[hi], as the pivot.
The variable i marks the boundary of the smaller values: the for loop walks the range and, whenever it finds a value below the pivot, swaps it with a[i] and moves the boundary on. At the end, the pivot goes into a[i], which is already its final place, and the two recursive calls sort each side if it has more than one element.
The var a: array of Integer parameter is an open array: it accepts arrays of any size and, being var, sorts them in place. The codes array is declared with its values already in it, which Free Pascal 3.2 also allows for dynamic arrays. On average quicksort makes about n·log n comparisons; in the worst case, with already sorted data and this pivot, it reaches n².
Binary search only works on sorted data: it looks at the middle element and discards the half where the target cannot be. Find does it recursively and returns -1 with Exit(-1) once the range is empty. With a million codes, about 20 comparisons are enough.
Code · main.pas
program main;procedure QuickSort(var a: array of Integer; lo, hi: Integer);var i, j, tmp: Integer;begin i := lo; for j := lo to hi - 1 do if a[j] < a[hi] then // a[hi] is the pivot begin tmp := a[i]; a[i] := a[j]; a[j] := tmp; Inc(i); end; tmp := a[i]; a[i] := a[hi]; a[hi] := tmp; // the pivot to its final place if lo < i - 1 then QuickSort(a, lo, i - 1); // smaller values, on the left if i + 1 < hi then QuickSort(a, i + 1, hi); // bigger ones, on the rightend;function Find(const a: array of Integer; target, lo, hi: Integer): Integer;var mid: Integer;begin if lo > hi then Exit(-1); // nothing left to look at mid := (lo + hi) div 2; if a[mid] = target then Result := mid else if a[mid] < target then Result := Find(a, target, mid + 1, hi) else Result := Find(a, target, lo, mid - 1);end;var codes: array of Integer = (4021, 1187, 9350, 2764, 5512, 3308, 7045); code: Integer;begin QuickSort(codes, 0, High(codes)); for code in codes do Write(code, ' '); WriteLn(LineEnding, '5512 is at index ', Find(codes, 5512, 0, High(codes))); WriteLn('6000 is at index ', Find(codes, 6000, 0, High(codes)));end.Output · fpc main.pas && ./main
1187 2764 3308 4021 5512 7045 9350 5512 is at index 4 6000 is at index -1
Key points
- Quicksort: partition around a pivot and sort each side.
- After partitioning, the pivot is already in its final place.
var a: array of Integeraccepts arrays of any size.- Binary search needs sorted data.
- Each step of binary search throws away half.
Exercise
Change QuickSort's comparison to sort from largest to smallest, and adapt Find so it still works with that order.