Question

Task1: Ternary Partition

Write a function ternary partition(lst) that partitions an unsorted list into three sections: smaller than pivot, equal to pivot, larger than pivot.

Input: an unsorted list containing one or more integers.

Output: a pair of integers, where the first integer is the index of the final position of the pivot, and the second integer is the index of the first element that is larger than the pivot. The pivot should be the element in the 0th position in the original list. To receive full marks the original list must be partitioned; however, the list is not returned.

Examples

a) Let lst1=[3]. Calling ternary partition(lst1) returns (0,1), as after calling function lst1=[3], thus the pivot section starts at 0 and ends at 1 (exclusive).

Answer 1

SOLUTION a:

##define a function for ternary partiton
##i am doing it in the same basis as quick sort
def ternaryPartition(a):
pivotIndex=0 ##store the pivotIndex with the intial index
pivot=a[0] ##store the pivot
  
for i in range(len(a)):
if(a[i]<pivot):
## if an item is less than pivot swap the details and increase the index   
pivotIndex=pivotIndex+1
##swap the current index value with the pivotIndex
a[i],a[pivotIndex]=a[pivotIndex],a[i]
## Here we are not swapping the pivot value with the lesser value since it will not check if the previous values are greater
##we are doing swap with the lesser so if the value is greater then it will in the pivotIndex and the pivot will be in the
## zero index itself
  
## we need to swap the pivot index with the zero index so that the data is in the
a[pivotIndex],a[0]=a[0],a[pivotIndex]
print(a)
pivotGreater=pivotIndex+1
##if there are some elements that are equal to the pivot then the index of the
##elements that are greater than pivot will change to check that we are using this
for i in range(pivotIndex,len(a)):
if(a[i]==pivot):
##if the elemets are equal to pivot we need to continue
continue
else:
## this for checking for the index of the element that are greater than the pivot
pivotGreater=i
break
##partion List like this

lessThanPivot=a[0:pivotIndex]
equalPivot=a[pivotIndex:pivotGreater]
greaterThanPivot=a[pivotGreater:]
print("List less than Pivot",lessThanPivot)
print("Equal List",equalPivot)
print("Greater than pivot list ",greaterThanPivot)
##returning the pivot index and index of the element where the data is greater than pivot
##we are returning an map here
return (pivotIndex,pivotGreater)
  

li=list(map(int,input("Enter list").split(" ")))
##reading input and then casting it to int
##since map returns an map so we are convrting it to list

##calling the function
print("Returning data from ternary function",ternaryPartition(li))
     
  
EXPLANATION:

I have written the explanation on each step of the
I have printed the list by partitioning

partion list is written with three names in the program and not returned

SOURCE CODE:

  

OUTPUT: