Statement

Giorgio is working on a research paper which involves the partition step of the Quicksort algorithm. The partition step works like this: we choose some element of the array (it doesn't matter which one), which will then be called pivot element. Then we move all the array elements in such a way that, in the end: (1) all the elements on the left of the pivot are smaller than it; (2) all the elements on the right of the pivot are greater than it. For example, let's take this array: 2, 6, 1, 5, 7, 8, 9, 4, 3. Let's say we choose the second element as pivot (the one with value 6). On the left, there is only one element with value 2, which is smaller than 6, so the "left partitioning" is already satisfied. On the right, however, there are some elements which are not grater than 6, so we should move them in order to obtain a correct partition. So, a valid partition (among many) of the array is this: 2, 3, 4, 1, 5, 6, 9, 7, 8...