Question
(Partition of a list) Write the following function that partitions the list using the first element, called a pivot:
def partition(lst):
After the partition, the elements in the list are rearranged so that all the elements before the pivot are less than or equal to the pivot and the element after the pivot are greater than the pivot. The function also returns the index where the pivot is located in the new list. For example, suppose the list is [5, 2, 9, 3,6, 8]. After the partition, the list becomes [3, 2, 5, 9, 6, 8]. Implement the function in a way that takes len(lst) comparisons. Write a test program that prompts the user to enter a list and displays the list after the partition.
Here is a sample run:
Enter a list: 10 1 5 16 61 9 11 1
After the partition, the list is 9 1 5 1 10 61 11 16
Answer
Program code:
# Function to partition the list using the first element as a pivot
def partition(lst):
pivot = lst[0] # Set the pivot as the first element
low = 1 # Index for elements less than or equal to the pivot
high = len(lst) - 1 # Index for elements greater than the pivot
while high > low:
# Find the first element from the left greater than the pivot
while low <= high and lst[low] <= pivot:
low += 1
# Find the first element from the right less than the pivot
while low <= high and lst[high] > pivot:
high -= 1
if high > low:
# Swap the elements
lst[low], lst[high] = lst[high], lst[low]
while high > 0 and lst[high] >= pivot:
high -= 1
if pivot > lst[high]:
# Swap the pivot with the element at the high index
lst[0], lst[high] = lst[high], lst[0]
return high
# Test program
def main():
# Prompt the user to enter a list
lst = list(map(int, input("Enter a list: ").split()))
# Partition the list
pivotIndex = partition(lst)
# Display the list after the partition
print("After the partition, the list is:", end=" ")
for number in lst:
print(number, end=" ")
# Call the test program
main()
Executed Output:
Enter a list: 10 1 5 16 61 9 11 1
After the partition, the list is: 9 1 5 1 10 61 11 16