Hello please help with this problems with 6 points and 10 po

Solution

(6 Points)

The two partitioning techniques are

Hoare Partitioning - Here the last element in the list is chosen as the pivot

This uses two indexes, one starts at the beghinning and other at the end of the list. They are iterated and moved towards each other, until they detect an inversion of the two elements, one greater than the pivot, and other smaller, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index.

This uses less swaps compared to lomuto partitioning. It has worst case of O(n^2) when the array is sorted.

Lomuto Partitioning - Here the last element in the list is chosen as the pivot

The list is iterated and each time an element less than or equal to pivot is found, the index of the pivot is incremented and that element would be placed before the pivot. Worst case of O(n^2) when the list is sorted or the list has maximum duplicate elements.

Both methods can be implemented using n1 comparisons to partition an array of length n as we need to compare every element to the pivot for deciding where to put it.