Data structures What purpose does partition function serve in relation to the qu

Question

Data structures What purpose does partition function serve in relation to the quicksort algorithm? More specifically what does the partition function guarantee about the pivot point and how do we utilize the return value in implementing Quicksort? Data structures What purpose does partition function serve in relation to the quicksort algorithm? More specifically what does the partition function guarantee about the pivot point and how do we utilize the return value in implementing Quicksort? What purpose does partition function serve in relation to the quicksort algorithm? More specifically what does the partition function guarantee about the pivot point and how do we utilize the return value in implementing Quicksort?

Explanation / Answer

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Pseudo Code for recursive QuickSort function :
/* low --> Starting index, high --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
pi = partition(arr, low, high);

quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}

We use index returned by partation in further to call Quicksort for subproblem (left and right parts of index)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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