1 IE170 Lecture 8 2

• We now discuss a sorting algorithm called quicksort similar to one that we saw in Lab 2. • The basic quicksort algorithm is as follows. – Choose a partition element. – Partition the input array around that element to obtain two subarrays. – Recursively call quick sort on the two subarrrays. • Here is code for the basic algorithm. void quicksort(Item * data, const int l, const int r) if (r < = l) return; int i = partition(data, l, r); quicksort(data, l, i-1); quicksort(data, i+1, r);