Quick sort is one of the well known generic sorting algorithm in practice. It is

Question

Quick sort is one of the well known generic sorting algorithm in practice. It is popular since it is average running time is O(nlogn) << O(n2), and most of the time, it generates the results in a quick time.

As you read from your textbook, running time of Quick sort strictly depends on the performance of the partitioning algorithm (the way we select the pivot). In the worst case scenario, your partitioning algorithm might pick the lowest or the highest number in the unsorted array, then the Quick sort algorithm may end up with O(n2) complexity. However, if we can find a way that we can find the median element in the array in linear time, then running time of Quick sort will be ?(nlogn).

Since partitioning is so crucial for Quick sort, my question is: Can we find the median element in an unsorted array in linear time? If so, how? Please discuss the approach here. If not, then please explain why you think that it is not possible.

Explanation / Answer

Yes, median can be found in O(n) time of an unsorted array. The algorithm to find median in O(n) works similar to quicksort. In quicksort partitioning the array takes O(n) using pivot element and then working upon the partitioning takes O(logn). In the algorithm to find median we can work in a similar fashion by dividing array into partitions one by one lick quicksort, but in quicksort you work on both the partitions to sort the both partitions. Here recurse only through one partition which will have median element and recurse until there is only one element left in the partition and that will be the median element of the array. Since this uses only paritioning of quicksort, this also also runs in O(n)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.