Use the Hoare paritioning algorithm to partition the list 3 29 2 49 36 4 14 6 9

Question

Use the Hoare paritioning algorithm to partition the list 3 29 2 49 36 4 14 6 9 12 for the pivot value 3. Also perform Lomuto's partition. Do the partitions produced by Lomuto and Hoare look the same? Perform Lomuto and Hoare partition on the following list: 1 1 2 1 1. How are they different? How would this affect Quicksort's performance on list with lots of repetitions? Use the Hoare paritioning algorithm to partition the list 3 29 2 49 36 4 14 6 9 12 for the pivot value 3. Also perform Lomuto's partition. Do the partitions produced by Lomuto and Hoare look the same? Perform Lomuto and Hoare partition on the following list: 1 1 2 1 1. How are they different? How would this affect Quicksort's performance on list with lots of repetitions?

Explanation / Answer

Using Hoare partition on pivot 3.

1. i=1, pivot= A[1]=3

2. j=10.

3. do

4. { i = i + 1

5 }while(arr[i] < pivot)

6. do{

7 j=j-1

8. }while(arr[i] > pivot)

9. if(i>=j)

10 then return j

11. Swap A[i] with A[j].

Iteration=1: i=1 j=10.. j=j-1 till j=3

here exchange A[1] and A[3]

iteration 1 will finish here. array will be partioned at j=1.

Using lomuto's Partition on pivot= 12:

iteration1 : i=0, j=1.

i=2,j=3

i=3, j=6

i=4,j=8

i=5,j=9

i=6,j=10

return i=6.

on input A= {1,1,2,1,1}

Hoare partition gives the same list repeatedly.to quicksort for first 3 calls. after that the list will change to {1,1,1,1,2}

Lomuto partition gives sorted output in first iteration. i.e {1,1,1,1,2}

3 29 2 49 36 4 14 6 9 12

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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