1

quickSelectアルゴリズム用に次の擬似コードが与えられました。いくつかのことについて少し混乱しています。quickSelectメソッドを呼び出すと、「k」に対して何を送信しますか。また、メソッドの最初でcount = 0を宣言する必要があるため、quickSelectの再帰呼び出しで常に0に戻されますが、これは必要なことではありません。助けてくれてありがとう、Pseudoを含めました。 -コードと以下の私のコード。

Function quickSelect(aList, k):
If aList is not empty:
    pivot <- Choose the element at position (len(alist)//2)
    smallerList <- All elements of aList smaller than pivot
    largerList <- All elements of aList larger than pivot
    count <- the number of occurences of pivot value in aList
    m <- the size of smallerList
    if k >= m and k < m + count then:
        return pivot
    if m > k:
        return quickSelect(smallerList,k)
    else:
        return quickSelect(largerlist, k-m-count)

これは私が思いついたものです：

def quickSelect(aList, k):
   pivot = aList[len(aList)//2]
   smallerList = aList[:pivot]
   largerList = aList[pivot:]
   m = len(smallerList)
   count = 0

   for i in aList:
      if i == pivot:
        count = count + 1

   if k >= m and k < m + count:
      return pivot
   if m > k:
      return quickSelect(smallerList, k)
   else:
      return quickSelect(largerList, k-m-count)
4

1 に答える 1

6

まず、値ではなくインデックスに基づいて、ピボットの両側からコンテンツを取得しますsmallerList。largerListピボットは、インデックスの位置ではなく、インデックスの内容で数値を分割することになっています (たとえば、インデックスが 5 の場合、数値 5 未満のすべてのエントリを に割り当てる必要がsmallerListあり、それより大きいすべての数値をそれに割り当てる必要があります) largerList。は 5 より大きい。

これは単純な for ループで実行できます。

if len(aList)!=0:
pivot=aList[(len(aList)//2)]
smallerList = []
for i in aList:
    if i<pivot:
        smallerList.append(i)
largerList=[]
for i in aList:
    if i>pivot:
        largerList.append(i)
m=len(smallerList)
count=len(aList)-len(smallerList)-len(largerList)

smallerListピボットをlargerList含む / 含まない / ため、カウント (ピボットが発生する回数) は、メイン リストの長さから小さいリストと大きいリストの合計の長さを引いたものになります。

ここで、k (k 番目に小さい数) が小さい方のリストの長さである m 以上であり、かつ k が小さい方のリストの長さ + ピボットの数より小さい場合、ピボットを返す必要があります。探していた k 番目に小さい数。

if k >= m and k<m + count:
    return pivot

または、小さい方のリストの長さが k より大きい場合はsmallerList、完全なリストではなく、 のみを使用してクイック選択を再度実行します。

elif m > k:
    return quickSelect(smallerList,k)

それ以外の場合は、完全なリストではなく、大きい方のリストを使用して再度クイック選択を実行し、k - 小さい方のリストの長さ - ピボットの数を探します。

else:
    return quickSelect(largerList, k - m - count)

この関数は何度も実行され (線形ソートよりもはるかに高速)、満足するとピボットが返されます。この場合のピボットは中央値になります。

お役に立てれば！

于 2012-10-17T15:33:09.290 に答える