在python中为Quicksort创建分区函数

Hi I am not able to create partition function for quicksort in python. I've searched on many websites but am not able to understand what is going on. I tried to do it but am stuck here.

嗨,我无法在python中为quicksort创建分区函数。我在许多网站上搜索过,但我无法理解发生了什么。我试着这样做,但我被困在这里。

totalElem = input("Enter total Elements: ")
c = 0
unsortElem = [0]*totalElem
low = 0
high = totalElem - 1

# This is to input elements
for c in range(totalElem):
    unsortElem[c] = input("Enter Number: ")
    c += 1

# The swap function
def swap(elem1, elem2):
    k=elem1
    elem1 = elem2
    elem2 = k

def partition(list, low, high):
    left = low
    right = high
    pivot = (low+high)/2
    pivotElem = list[pivot]
    while(left<right):
        while(list[left]<pivotElem):
            left += 1
        while(list[right]>pivotElem):
            right += 1
        if(list[left]>list[right]):
            swap(left, right)


#The below prints are just to check if the function is getting correct values.
    print list
    print pivotElem
    print left
    print len(list)



partition(unsortElem, low, high)

1 个解决方案

#1

There are several mistakes in your code - firstly, your right += 1 is wrong, since right is the highest index. You need to decrease the value, not increase. Secondly, why are you increasing c in input? You are using range, so it does it automatically. Also, you don't need your own swap function, since Python can do it, and list is a type, so you can't name your variable like that.

您的代码中存在多个错误 - 首先,您的权利+ = 1是错误的,因为右边是最高的索引。你需要减少价值,而不是增加。其次,为什么你在输入中增加c?您正在使用范围,因此它会自动执行。此外,您不需要自己的交换功能,因为Python可以执行此操作,而list是一种类型,因此您无法像这样命名变量。

What you are trying to do is recursively sort elements smaller and bigger than your pivot. If you find larger element on the beginning of the list than pivot, you stop, the same for smaller element from the end of the list, then you swap the values (since they are in bad parts of your list). You also need to take care if there are more same elements. Your partition function doesn't do only partitioning, since you are swapping elements there, it's more like not correct quicksort function without recursive calls.

你要做的是递归地排序比你的支点更小和更大的元素。如果您在列表的开头找到比枢轴更大的元素,则停止,对于列表末尾的较小元素,相同,然后交换值(因为它们位于列表的坏部分)。如果有更多相同的元素,您还需要注意。您的分区功能不仅仅进行分区,因为您在那里交换元素,更像是没有正确的快速排序功能而没有递归调用。

totalElem = int(raw_input("Enter total Elements: "))
unsortElem = []

# This is to input elements
for c in range(totalElem):
    unsortElem.append(int(raw_input("Enter Number: ")))

def qsort(mylist, low, high):
    if high - low < 1:   # there is less than 2 elements
        return
    left = low
    right = high
    pivotElem = mylist[(low + high) / 2]
    while left <= right:
        while mylist[left] < pivotElem:
            left += 1
        while mylist[right] > pivotElem:
            right -= 1
        if left <= right and mylist[left] >= mylist[right]:
            mylist[left], mylist[right] = mylist[right], mylist[left]
            left += 1
            right -= 1
    qsort(mylist, low, right)
    qsort(mylist, left, high)


qsort(unsortElem, 0, len(unsortElem) - 1)
print unsortElem

You didn't mention if you are using Python 3 or Python 2. This is corrected for Python 2, if you want it for Python 3, just use input instead of raw_input and braces for printing, eg print(unsortElem).

你没有提到你是使用Python 3还是Python 2.对于Python 2,如果你想要它用于Python 3,只需使用输入而不是raw_input和大括号进行打印,例如print(unsortElem)。