1. Modified partition. (a) Write a modified version of the partition algorithm t

Question

1. Modified partition. (a) Write a modified version of the partition algorithm that splits the list in three parts instead of two, using the first and last elements of the list as pivots. Your modified partition algorithm must work in linear time. (b) Write a modified version of quicksort that uses your modified partition algorithm. (c) Write a recurrence relation for the best case time complexity of your modified quicksort algorithm (d) Solve the recurrence relation for your modified quicksort algorithm

Explanation / Answer

partition (arr[], low, high)

{

    // pivot (Element to be placed at right position)

    pivot = arr[high];

    i = (low - 1) // Index of smaller element

    for (j = low; j <= high- 1; j++)

    {

        // If current element is smaller than or

        // equal to pivot

        if (arr[j] <= pivot)

        {

            i++;    // increment index of smaller element

            swap arr[i] and arr[j]

        }

    }

    swap arr[i + 1] and arr[high])

    return (i + 1)

}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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