Алгоритм быстрой сортировки с двумя указателями - PullRequest
Новая
       11

Алгоритм быстрой сортировки с двумя указателями

1 голос
/ 19 апреля 2020

Можете ли вы помочь мне с этой задачей? Это из книги Р. Седжвика «Введение ВВЕДЕНИЕ В ПРОГРАММИРОВАНИЕ В PYTHON Апдисциплинарный подход»

Разделение. Составьте функцию, которая сортирует массив, который, как известно, имеет не более двух разных значений. Подсказка: сохраняйте два указателя, один из которых начинается с левого конца и двигается вправо, а другой начинается с правого конца и двигается влево. Поддерживайте инвариант, чтобы все элементы слева от левого указателя были равны меньшему из двух значений, а все элементы справа от правого указателя равны большему из двух значений.

Так что я придумал это, но это не работает. Где я не прав? Я полагаю, это вызвано тем, что два метода quickSort2 вызываются друг за другом (я добавил туда несколько комментариев). 

import sys      

def quickSort2(arr, left, right, n, direction):
    if n == 1:
        return
    if left > right:
        return
    if left == right:
        print ("left ")
        print([i for i in arr[len(arr)-n:left]])
        print ("right ")
        print([i for i in arr[left+1:len(arr)]])
        print ("pivot ")
        print(arr[left])

        quickSort2(arr, len(arr)-n, left-1, left-len(arr)+n, True) # Is this ok?
        quickSort2(arr, left+1, len(arr)-1, len(arr)-left-1, True) # Is this ok?

        return
    if direction:
        if arr[left] < arr[right]:
            quickSort2(arr, left+1, right, n, True)
        #elif arr[left] > arr[right]:
        else:
            arr[left], arr[right] = arr[right], arr[left]
            quickSort2(arr, left, right-1, n,  False)
    else:
        if arr[left] < arr[right]:
            quickSort2(arr, left, right-1, n,  False)
        #elif arr[left] > arr[right]:
        else:
            arr[left], arr[right] = arr[right], arr[left]
            quickSort2(arr, left+1, right, n, True)



if __name__ == "__main__":
    #array = [5,4,5,4]
    #array = [5,4,5,4,4,5,4]
    #array = [5,5,4,5,5,5,5,4,5,5,4,5,4,4,4,4,4,4,5,5,4,5,4]
    array = [5,4,4,1,7,4,3,8,3,1]

    quickSort2(array, 0, len(array) - 1, len(array),  True)
    for i in array: print (i, end = " ")

Например, для массива = [5,5,4,5,5,5,5, 4,5,5,4,5,4,4,4,4,4,4,5,5,4,5,4] возвращается 

4 4 4 4 4 4 4 4 4 4 5 4 5 5 5 5 5 5 5 5 5 5 5

1 Ответ

1 голос
/ 19 апреля 2020

Вопрос не требует от вас реализации алгоритма быстрой сортировки, он просто требует, чтобы вы разбили список, который имеет не более двух разных значений . Важный бит в подсказке:

Поддерживать инвариант, что все элементы слева от левого указателя равны меньшему из двух значений, а все элементы справа от правого указателя равны равно большему из двух значений.

Это то, что вы не гарантируете своим алгоритмом. Давайте рассмотрим ваш пример: что произойдет, если левый и правый индексы будут указывать на 5, а ваше текущее направление - справа налево. Это предложение if будет выполнено: 

arr[left], arr[right] = arr[right], arr[left]
quickSort2(arr, left+1, right, n, True)

Таким образом, вы меняете значения (что не имеет никакого эффекта, поскольку они равны) и увеличиваете индекс left на единицу. И вот в чем проблема: вы нарушили инвариант: слева от левого указателя стоит 5.

Я предлагаю удалить direction, так как он не нужен, и добавить два новых переменные, чем меньше и больше значение. При этом вы всегда будете знать, можете ли вы двигаться дальше или указатель должен оставаться в своем текущем индексе.

Также я переименовал функцию в partition, поскольку это лучше соответствует упражнению. 

def partition(arr, smaller, larger, left, right, n):
    if left >= right:
        # the two pointers met, the array is partitioned
        return
    if arr[left] == smaller:
        # move left pointer to the right
        partition(arr, smaller, larger, left+1, right, n)
    elif arr[right] == larger:
        # move right pointer to the left
        partition(arr, smaller, larger, left, right-1, n)
    else:
        # when we find a larger on the left and a smaller on the right, we swap
        arr[left], arr[right] = arr[right], arr[left]
        # and move both pointers forward
        partition(arr, smaller, larger, left+1, right-1, n)
...