2

オランダの国家旗アルゴリズムを使用してクイックソート風のアルゴリズムをプログラムしようとしています。私はこの仕事をするためにできる限りのことを試みました、そして私は本当に欲求不満になっています。見て、バグを見つけるのを手伝ってくれませんか？

import random

a = []
for i in range(100):
    a.append(random.randint(1, 100))

print(a)
def partion(array, left, right, lPiv, rPiv):
        high = len(array) -1
        p = left
        i = left
        while i < high:
                if array[i] < lPiv and array[i] < rPiv:
                        array[i],array[p]=array[p],array[i]
                        p = p+1
                        i = i+1
                elif array[i] > lPiv and array[i] > rPiv:
                        array[i],array[high]=array[high],array[i]
                        high = high-1
                else:
                        i = i+1

        return [p, high]

def piv(array, left, right):
    aMin = array[left]
    aMax = array[left]

    for i in array:
      if i < aMin:
          aMin = i
      if i > aMax:
          aMax = i
    return [aMin + ((aMax - aMin) /3), aMin + ((aMax-aMin)/3)*2]


def sort(array, left, right, depth):
    apiv = piv(array, left, right)
    part = partion(array, left, right, apiv[0], apiv[1])
    if right-left >= 3:
        piv1 = piv(array, left, part[0])
        part1 = partion(array, left, part[0], piv1[0], piv1[1])
        sort(array, left, part1[0], depth+1)


        piv2 = piv(array, part[0], part[1])
        part2 = partion(array, part[0], part[1], piv2[0], piv2[1])
        sort(array, part[0], part[1])

        piv3 = piv(array, part[1], right)
        part3 = partion(array, part[1], right, piv3[0], piv3[1] )
        sort(array, part[1], right)

    elif right-left < 3:
        if array[right] < array[left]:
            array[right],array[left] = array[left], array[right]
        else:
            return


sort(a, 0, len(a), 1)
print(a)
4

2 に答える 2

1

コードのいくつかのバグ

  1. sort（）は4つのパラメーターを受け取るため、sort（array、part [0]、part [1]）は失敗します。ところで深さは必要ありません。
  2. if array[right] < array[left]:およびsort(a, 0, len(a), 1)。右が配列の長さである場合、右は配列のインデックス範囲外です。
  3. pivは、配列全体ではなく、パーティションを処理する必要があります
  4. パーティション内の番号がすべて同じでaMin + ((aMax - aMin) /3)、aMin + ((aMax-aMin)/3)*2同じインデックスである場合
  5. high = len(array) -1パーティションは配列全体ではなくパーティションのみを処理するため、high = right -1
  6. part1 = partion(array, left, part[0], piv1[0], piv1[1])間違っている。Sort（）は、配列を最初にパーティション化します。同じ再帰で2回パーティション化しないでください。sort（array、...）を呼び出すだけです。
  7. あなたのパーティションpartitionalgorithmが間違っていて、私はそれの簡単な修正を見つけることができません

これが私の実装です。

import random
from itertools import islice
a = []
for i in range(100):
    a.append(random.randint(1, 100))

def partition(array, left, right, lPiv, rPiv):
        q = right -1
        p = left
        r = left
        while p<=q:
            if array[p]<=lPiv:
                array[p], array[r] = array[r], array[p]
                p = p+1
                r = r+1
            elif lPiv<array[p]<=rPiv:
                p = p+1
            else:
                array[p], array[q] = array[q], array[p]
                q=q-1

        return (p, q+1)

def piv(array, left, right):
    aMin = min(islice(a,left,right))
    aMax = max(islice(a,left,right))
    return (aMin + ((aMax - aMin) /3.0), aMin + ((aMax-aMin)/3.0)*2)


def sort(array, left, right):
    if right-left >= 3:
        piv_left, piv_right = piv(array, left, right)
        if piv_left == piv_right:
            return
        pt_left, pt_right = partition(array, left, right, piv_left, piv_right)
        sort(array, left, pt_left)
        sort(array, pt_left, pt_right)
        sort(array, pt_right, right)
    elif right-left <3:
        if left<right and array[right-1] < array[left]:
            array[right-1],array[left] = array[left], array[right-1]


sort(a, 0, len(a))
print a

#test
assert( a==sorted(a) )
于 2012-05-21T05:09:36.440 に答える
0

pivは常に同じ値を返すようですよね？たぶん、forループは配列全体ではなくarray [left：right]の上にあるべきですか？

于 2012-05-21T04:43:22.240 に答える