I am extremely confused. One of the quiz question was "True or False, Quick sort achieves sorting during the conquer stage of the algorithm" and I chose true because I remember reading:
The three steps of Quicksort are as follows:
Divide: Rearrange the elements and split the array into two subarrays and an element in between such that so that each element in the left subarray is less than or equal the middle element and each element in the right subarray is greater than the middle element.
Conquer: Recursively sort the two subarrays.
Combine: None.
However, the answer to the quiz says that the answer is False without any explanation...
As the text book says that QuickSort follows divide and conquer algorithm in which conquer stage recursively sort the two subarrays, shouldn't the answer be true?
any enlightenment would be appreciated.
Quicksort picks a pivot, puts everything smaller on the left and everything bigger on the right.
This is the divide step you are referring to.
The conquer part is to recursively do this on the left and right subsets.
However, during the divide step, the elements are already being sorted (smaller on left, bigger on right), and quicksort works because recursively doing so ensures everything is in its right place.
The definition is not wrong, because the conquering repeats this on the left and right, but the divide part is what really splits and rearranges them, as stated.