Question

from partition import partition

def quicksort(a: list, l: int, u: int) -> None:
  '''Sort the given list a in non-descending order.
  Precondition: 0 <= l and u < len(a)'''

  if l < u:
    mid = (l + u) // 2
    three = [a[l], a[mid], a[u]]
    three.sort()
    if three[1] == a[l]:
      pivot_loc = l
    elif three[1] == a[u]:
      pivot_loc = u
    else:
      pivot_loc = mid
    a[u], a[pivot_loc] = a[pivot_loc], a[u]
    pivot = a[u]    
    i = partition(a, l, u - 1, pivot)
    a[i], a[u] = a[u], a[i]
    quicksort(a, l, i - 1)
    quicksort(a, i + 1, u)

from typing import List, Any, Tuple

def partition (a: List, l: int, u: int, pivot: Any) -> Tuple[int, int]:
  """
  Alternate partition: This new partition procedure maintains two
  split points, dividing the list into those elements that are smaller
  than the pivot, those exactly equal to the pivot, and those strictly
  larger than the pivot. Return a tuple of the indices of the two split points.

  >>> l = [-19, 1, 1, 1, 18, 18, 104, 418]
  >>> partition(l, 0, len(l)-1, 18)
  (4, 6)
  >>> l
  [-19, 1, 1, 1, 18, 18, 418, 104]
  """
  
  i = l
  j = l
  k = u
  while j <= k:
    if a[j] < pivot:
      a[i], a[j] = a[j], a[i]
      i += 1
      j += 1
    elif a[j] == pivot:
      j += 1
    else:
      a[j], a[k] = a[k], a[j]
      k -= 1
  return (i, j)

Q.The quicksort has some mistakes.Modify the quicksort according to the partition function given below.

Answer 1

Program code to copy

from partition import partition



def quicksort(a: list, l: int, u: int) -> None:

    '''Sort the given list a in non-descending order.

    Precondition: 0 <= l and u < len(a)'''



    if l < u:

        mid = (l + u) // 2

        three = [a[l], a[mid], a[u]]

        three.sort()



        ''''

        Searching for appropriate pivot location. 

        '''

        if three[1] == a[l]:

            pivot_loc = l

        elif three[1] == a[u]:

            pivot_loc = u

        else:

            pivot_loc = mid


        ''''

             I have commented below line which was in actual question 

             as it not required to change value pivot location which 

             is already determined. 

        '''

        # a[u], a[pivot_loc] = a[pivot_loc], a[u]


        pivot = a[pivot_loc]

        #Two variables are required to hold two return values of function

        i, mid = partition(a, l, u , pivot)



        ''''

            Interchanging these value was defeating purpose of Sorting.  

        '''

        # a[i], a[u] = a[u], a[i]



        if (i+1)!=mid:

            quicksort(a, l, i - 1)

            #function call is changed according to two returned partitioned values.

            quicksort(a, mid+1, u)

        else:

            #To handle the case without any duplicate value

            quicksort(a, l, i - 1)

            quicksort(a, mid , u)







print("Input Array:", end = " ")

l =   [-1, 13, 1, 89, 18, 15, 104, 500]

print(l)



print("Output Array:", end = " ")

quicksort(l, 0, len(l)-1)

print(l)

NO change in partition function. Keep Partition.py in same directory to import.

Partition.py has the same code as in question.

Program Screenshot

Program Output

Considering different input cases