What does this line of code do?


#1

Hi,

Here is the exercise:

22%20PM

Here is the author’s solution to the exercise:

def main():
    s = input("Enter a list: ")
    items = s.split() # Extracts items from the string
    list = [ eval(x) for x in items ] # Convert items to numbers

    partition(list)

    print("After the partition, the list is ", end = "")
    for e in list:
        print(e, end = " ")

def partition(list):
    pivot = list[0]  # Choose the first element as the pivot
    low = 1  # Index for forward search
    high = len(list) - 1  # Index for backward search

    while high > low:
        # Search forward from left
        while low <= high and list[low] <= pivot:
            low += 1

        # Search backward from right
        while low <= high and list[high] > pivot:
            high -= 1

        # Swap two elements in the list
        if high > low:
            list[high], list[low] = list[low], list[high]

    while high > 1 and list[high] >= pivot: 
        high -= 1      


    # Swap pivot with list[high]
    if pivot > list[high]:
        list[0] = list[high]
        list[high] = pivot


main()

I do not understand what is the purpose of this block near the end of the program:

    while high > 1 and list[high] >= pivot: 
        high -= 1      

From my understanding when high < low, this means that the pivot and all the elements less than the pivot are on one side and the elements greater than the pivot are greater on the other side. But what is the purpose of this block? I stepped through the code and when it got to this block, it would only decrement by 1 when lst[high] had the same value as the pivot (so > is redundant. Should it not be ==?) What is the purpose of this block?

Thanks.


#3

How exactly do they count comparisons there? Because that does 14 comparisons between list elements for the example input (it’s less than double the length, but it seems to say only 8 are allowed)
The loop you ask about should be an if-statement. A return statement is also missing.
The exercise statement doesn’t say that it should be in-place, so a simpler solution is to sort into high and low (one comparison for each element except the pivot) and then write them back into the original list with the pivot in the middle.


#4

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.