Project 5 COMP 110 Copyright 2017 © Majid Haghoo 1 Project 5 – Quick Sort 1

Project 5 COMP 110 Copyright 2017 © Majid Haghoo 1 Project 5 – Quick Sort 1. Quick sort is a recursive method to sort arrays. (data, in general) 2. First, function QuickSort chooses an element, called pivot. 3. Array elements are swapped until: 1. The pivot element falls in its correct position. 2. All elements less than pivot will be to the left of the pivot. 3. All elements greater than pivot shifted to the right of the pivot. 4. Then the function calls itself recursively to sort left side. 5. Then the function calls itself recursively to sort right side. 2 Copyright 2017 © Majid Haghoo Project 5 – Quick Sort: Details 1. Key to this sort is a method called Partition. 2. This method swaps the array elements until it finds a right place for the pivot element. 3. Usually, the last element is chosen to be the pivot. 4. The elements are compared against pivot. 3 Copyright 2017 © Majid Haghoo Project 5 – Quick Sort: Details int Partition (int samples [], int first, int last) { int pivot = samples [last]; // Select last element as pivot int leftIndex = first; for (int j = first; j