на месте раздел не работает для дублирующих элементов

Question

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

Код выглядит так

def inplace_partitioning(input,l,r):
    len_a=len(input)
    pivot=input[l]
    i=l+1
    for j in range(l+1,r+1,1):
        if input[j]<pivot:#do nothing if new elem >pivot
            #swap new elem with leftmost elem greater than pivot
            temp=input[j]
            input[j]=input[i]
            input[i]=temp
            i+=1
    #swap pivot with rightmost elem lessthan pivot
    temp=input[l]
    input[l]=input[i-1]
    input[i-1]=temp

Когда ввод состоит из уникальных элементов, код дает правильные результаты

input=[5,6,3,1,8,4]
inplace_partitioning(input,0,len(input)-1)
print input

>>[4, 3, 1, 5, 8, 6]

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

input=[5,6,3,1,8,5]
>>>[1, 3, 5, 6, 8, 5]

Это потому, что моя реализация ошибочна? Может кто-нибудь немного помочь?

Answer 1

Я не совсем понял ваш алгоритм, и он не похож на разделение на основе быстрой сортировки.Обычно вы запускаете i и j в разных направлениях, один начинается с верхней части интервала, а другой - с нижней, но если я правильно понимаю, вы бежите в том же направлении.На первой итерации i и j имеют одинаковое значение, и если оно меньше, чем пивот, оно заменяется на себя (т. Е. Тот же эффект, как если бы оно НЕ было меньше шарнира)?

Answer 2

Это должно сделать

def partitionv(arr, l, r):

    p = r
    idx = l
    for i in range(l, r-1, 1):
        if arr[i] < arr[p]:
            arr[i], arr[idx] = arr[idx], arr[i]
            idx += 1
    arr[p], arr[idx] = arr[idx], arr[p]

    return arr

это раздел элемента справа.

Answer 3

if input[j]<pivot:

Это означает, что он будет перемещать числа влево от оси, только если они меньше.Однако вы хотите, чтобы числа, равные размеру оси, были перемещены, в противном случае числа, равные размеру точки, будут распределены по всей правой части точки.

измените его на:

if input[j]<=pivot: