Quicksort with median-of-three not sorting properly?-CodePudding

Please explain to me what I am doing wrong in my Quicksort code because the output array is not correctly sorted. It is using the median of three partitioning to select the pivot.

Here is the code:

def medianof3(arr, low, high):
  center = (low   high) // 2
  if arr[low] < arr[center]:
    arr[low], arr[center] = arr[center], arr[low]

  if arr[low] < arr[high]:
    arr[low], arr[high] = arr[high], arr[low]

  if arr[center] < arr[high]:
    arr[center], arr[high] = arr[high], arr[center]

  arr[center], arr[high - 1] = arr[high - 1], arr[center]

  return arr[high - 1]


def partition(array, low, high):

    # choose the rightmost element as pivot
    pivot = medianof3(array, low, high)

    # pointer for greater element
    i = low - 1

    # traverse through all elements
    # compare each element with pivot
    for j in range(low, high):
        if array[j] <= pivot:

            # If element smaller than pivot is found
            # swap it with the greater element pointed by i
            i = i   1

            # Swapping element at i with element at j
            (array[i], array[j]) = (array[j], array[i])

    # Swap the pivot element with the greater element specified by i
    (array[i   1], array[high - 1]) = (array[high - 1], array[i   1])

    # Return the position from where partition is done
    return i   1
 
# function to perform quicksort
 
 
def quickSort(array, low, high):
    if low < high:
 
        # Find pivot element such that
        # element smaller than pivot are on the left
        # element greater than pivot are on the right
        pi = partition(array, low, high)
 
        # Recursive call on the left of pivot
        quickSort(array, low, pi - 1)
 
        # Recursive call on the right of pivot
        quickSort(array, pi   1, high)
 
 
data = [1, 7, 4, 1, 10, 9, -2]
print("Unsorted Array")
print(data)
 
size = len(data)
 
quickSort(data, 0, size - 1)
 
print('Sorted Array in Ascending Order:')
print(data)

Output:

Unsorted Array: [1, 7, 4, 1, 10, 9, -2]

Sorted Array in Ascending Order: [1, 1, 7, 4, 9, 10, -2]

CodePudding user response：

The problem is that there is confusion in your code about what represents the rightmost element in a list. Is it at high or is it at high-1. Both assumptions can be found in your code, and obviously the mix breaks the correct algorithm.

In medianof3 the first few swaps indicate that high is included in the sublist, but then the final swap in that function makes a swap with the element at high-1... so you end up with a returned pivot that is not the rightmost element.

Then in partition the loop goes up to -- but excluding -- high. This is consistent with the assumption that the pivot sits at high. But then there is again a final swap with the element at high-1.

Then in quickSort the recursive calls use the assumption that the last argument indicates an index that is included in the sublist to be sorted.

So all those high-1 have to be corrected to high. Then it will work.