Question

1. Using an example of 6 integer elements,

   1. Show how quick sort can be done. [4 Marks]

2. Describe the worst case scenario of quick sort [2 Marks]

3. In your answer at d (i), show what makes quick sort categorized as divide and conquer

[2 marks]

Answer 1

Consider the following array: 45,20,5,15,55,30 We need to sort this array in the most efficient manner without using extra place (inplace sorting).

Solution

Step 1:

• Make any element as pivot: Decide any value to be the pivot from the list. For convenience of code, we often select the rightmost index as pivot or select any at random and swap with rightmost. Suppose for two values “Low” and “High” corresponding to the first index and last index respectively.
  • In our case low is 0 and high is 5.
  • Values at low and high are 45 and 30 and value at pivot is 30.
• Partition the array on the basis of pivot: Call for partitioning which rearranges the array in such a way that pivot (30) comes to its actual position (of the sorted array). And to the left of the pivot, the array has all the elements less than it, and to the right greater than it.
  • In the partition function, we start from the first element and compare it with the pivot. Since 45 is greater than 30, we don’t make any change and move on to the next element 20.
  • Compare again with the pivot. Since 20 is less than 30, we swap 45 and 20. The array becomes 20, 45, 5, 15, 55, 30
  • We move on to the next element 9 which is again less than pivot (30) thus swapping it with 50 makes our array as 20, 5, 45, 15, 55, 30.
  • Similarly, for next element 15 which is less than 30, the array becomes 20, 5, 15, 45, 55, 30. Now 55 is greater than pivot (30), hence no changes.
  • Lastly, we swap our pivot with 45 so that it comes to the correct position.

Thus the pivot (30) comes at its actual position and all elements to its left are lesser, and all elements to the right are greater than itself.

Step 2: The main array after the first step becomes

20, 5, 15, 30, 55, 45

Step 3: Now the list is divided into two parts:

1. Sublist before pivot element
2. Sublist after pivot element

Step 4: Repeat the steps for the left and right sublists recursively. The final array thus becomes
5, 15, 20, 30, 45, 55

Worst case scenario: This happens when we encounter the most unbalanced partitions possible, then the original call takes n time, the recursive call on n-1 elements will take (n-1) time, the recursive call on (n-2) elements will take (n-2) time, and so on. The worst case time complexity of Quick Sort would be O(n²).

• Its work by selecting a pivot element from the array and partitioning the other elements into sub arrays, whether they are smaller or greater than the pivot. The the sub array are sorted recursively. That is why it came under divide and conqer approach.