Some Applications in Algorithmics

Quicksort is a fast sorting algorithm, widely used for internal sorting. The basic idea is the choice of a partitioning element K. For example, let us consider the integer sequence [Regnier, 1989]: 45, 677, 98, 43, 42, 41, 60, 130, 32, 67 and choose K = 67 as the partitioning element. Scanning the left sublist from left to right, one exchanges any key greater than K with a key of the right sublist, scanned from right to left. This builds a list where K has its final position, all the keys to its left (resp. to its right) being smaller (resp. larger) than K.The intermediate stages are: 45 32 677 67 45 32 60 98 130 677 67 45 32 60 43 42 41 98 130 677 67 45 32 60 43 42 41 98 130 677 67