Python:中位数为三的快速排序 [英] Python: Quicksort with median of three

问题描述

我正在尝试更改此快速排序代码以使用采用三的中位数"的数据透视.

I'm trying to change this quicksort code to work with a pivot that takes a "median of three" instead.

def quickSort(L, ascending = True): 
    quicksorthelp(L, 0, len(L), ascending)


def quicksorthelp(L, low, high, ascending = True): 
    result = 0
    if low < high: 
        pivot_location, result = Partition(L, low, high, ascending)  
        result += quicksorthelp(L, low, pivot_location, ascending)  
        result += quicksorthelp(L, pivot_location + 1, high, ascending)
    return result


def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    L[low], L[pidx] = L[pidx], L[low]
    i = low + 1
    for j in range(low+1, high, 1):
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

liste1 = list([3.14159, 1./127, 2.718, 1.618, -23., 3.14159])

quickSort(liste1, False)  # descending order
print('sorted:')
print(liste1)

但我不确定如何做到这一点.中位数必须是列表的第一个、中间和最后一个元素的中位数.如果列表有偶数个元素，则中间成为前半部分的最后一个元素.

But I'm not really sure how to do that. The median has to be the median of the first, middle and last element of a list. If the list has an even number of elements, middle becomes the last element of the first half.

这是我的中值函数:

def median_of_three(L, low, high):
    mid = (low+high-1)//2
    a = L[low]
    b = L[mid]
    c = L[high-1]
    if a <= b <= c:
        return b, mid
    if c <= b <= a:
        return b, mid
    if a <= c <= b:
        return c, high-1
    if b <= c <= a:
        return c, high-1
    return a, low

推荐答案

让我们先实现三个数的中位数，这样一个独立的函数.我们可以通过对三个元素的列表进行排序来实现，然后返回第二个元素，例如:

Let us first implement the median-of-three for three numbers, so an independent function. We can do that by sorting the list of three elements, and then return the second element, like:

def median_of_three(a, b, c):
    return sorted([a, b, c])[1]

现在对于范围 low .. high(包括 low，排除 high)，我们应该确定元素的用途我们应该构造三个的中位数:

Now for a range low .. high (with low included, and high excluded), we should determine what the elements are for which we should construct the median of three:

1. 第一个元素:L[low],
2. 最后一个元素L[high-1]，和
3. 中间元素(如果有两个，取第一个)L[(low+high-1)//2].

所以现在我们只需要将分区函数修补为:

So now we only need to patch the partitioning function to:

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot = median_of_three(L[low], L[(low+high-1)//2], L[high-1])
    i = low + 1  
    for j in range(low + 1, high, 1): 
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1  
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

编辑:确定三个元素的中值.

EDIT: determining the median of three elements.

三个元素的中位数是位于其他两个值中间的元素.因此，如果 a <= b <= c，则 b 是中位数.

The median of three elements is the element that is in the middle of the two other values. So in case a <= b <= c, then b is the median.

所以我们需要确定元素的排列顺序，这样我们才能确定中间的元素.喜欢:

So we need to determine in what order the elements are, such that we can determine the element in the middle. Like:

def median_of_three(a, b, c):
    if a <= b and b <= c:
        return b
    if c <= b and b <= a:
        return b
    if a <= c and c <= b:
        return c
    if b <= c and c <= a:
        return c
    return a

所以现在我们用四个 if 情况定义了三个的中位数.

So now we have defined the median of three with four if cases.

EDIT2:这仍然存在问题.执行主元后，将元素 L[i-1] 与原始代码(主元的位置)中的 L[low] 交换.但这当然不再起作用:因为现在枢轴可以位于三个维度中的任何一个.因此，我们需要使 median_of_three(..) 更智能:它不仅应该返回枢轴元素，还应该返回该枢轴的位置:

EDIT2: There is still a problem with this. After you perform a pivot, you swap the element L[i-1] with L[low] in your original code (the location of the pivot). But this of course does not work anymore: since the pivot now can be located at any of the three dimensions. Therfore we need to make the median_of_three(..) smarter: not only should it return the pivot element, but the location of that pivot as well:

def median_of_three(L, low, high):
    mid = (low+high-1)//2
    a = L[low]
    b = L[mid]
    c = L[high-1]
    if a <= b <= c:
        return b, mid
    if c <= b <= a:
        return b, mid
    if a <= c <= b:
        return c, high-1
    if b <= c <= a:
        return c, high-1
    return a, low

现在我们可以解决这个问题:

Now we can solve this problem with:

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    i = low + (low == pidx)
    for j in range(low, high, 1):
        if j == pidx:
            continue
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1 + (i+1 == pidx)
    L[pidx], L[i-1] = L[i-1], L[pidx] 
    return i - 1, result

EDIT3:清理它.

虽然上面的方法看起来可行，但它相当复杂:我们需要让 i 和 j 跳过"枢轴的位置.

Although the above seems to work, it is quite complicated: we need to let i and j "skip" the location of the pivot.

如果我们首先将主元移动到子列表的前面(因此移动到 low 索引)可能更简单:

It is probably simpler if we first move the pivot to the front of the sublist (so to the low index):

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    L[low], L[pidx] = L[pidx], L[low]
    i = low + 1
    for j in range(low+1, high, 1):
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

这篇关于Python:中位数为三的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！