PYTHON CODE

Task 1: Paired-pivot partition

You may not import any other libraries or modules.

Write a function paired partition(lst), in which it uses two pivots in this manner:

a) Pick an elements P1 and P2 called pivots from the list. (You may select the first element in the list as P1 and the last element in the list as P2)

b) Assume that P1 P2, otherwise swap it.

c) Reorder the list into three parts: those less than the smaller pivot, those larger than the larger pivot, and in between are those elements between (or equal to) the two pivots (as shown in Figure 1).

Input: an unsorted list containing one or more integers.

Output: a partitioned list as shown in Figure 1.

To receive full marks, this function must have a complexity of O(N), where N=len(lst).

Examples

a) Let lst1=[3,1,6,2,4,8,9,5], calling paired partition(lst1), returns [2,1,3,4,5,9,6,8].

b) Let lst2=[8,16,20,14,17,2,19,10,1,2], calling paired partition(lst2), returns [1,2,2,8,14,19,10,20,16,17].

c) Let lst3=[1,2,3,4], calling paired partition(lst3), returns [1,2,3,4].

Marks are given for the correct behavior of the function:

(a) 1 mark for an implementation without complexity of O(N) and partitioning is performed without in-place strategy.

(b) 3 marks for an implementation without in-place strategy and has a best and worst-case complexity of O(N).

(c) 4 marks for an implementation using in-place strategy and has a best and worst-case complexity of O(N).

P1 and P2 P2 som > P2 Figure 1: Paired-pivot partition