0

非比較ソートアルゴリズムについて考えていますが、自分で見つけたと思います。

Input: A[0...n] ranged from 0...n //ideally, I think it can be expanded to more general case later

Non-comparison-sort(A,n):
let B = [0...n] = [0]
for i in A:
    B[A[i]]=i

このアルゴリズムの後、配列 B の各要素は配列 A への参照を持ち、値が m の A[k] にアクセスする場合は、A[B[m]] を使用できます。

私はこのアイデアに出くわした最初の人ではないと確信しています.だから私の質問は、このアルゴリズムは何と呼ばれていますか?

前もって感謝します。

4

3 に答える 3

1

実際、あなたのアルゴリズムはソートアルゴリズムではありません。の順列の逆数を計算するアルゴリズム0..nです。つまり、すべての数字を配置するために A を再配置する方法を教えてくれます。

ソートアルゴリズムではないのはなぜですか? A に範囲 0..n のすべての数値が含まれる場合、並べ替えられた配列は常に B = [0, 1, 2, ..., n] になります。一方、A に重複がある場合、このアルゴリズムは機能しません。あなたがやろうとしていることは、 sort を数えることだと思います。kこのアルゴリズムは、 A が size の配列で、範囲内の数値を含む場合に適しています0..n。アルゴリズムにはサイズの配列 B があり、n+1A を 1 回反復しながら、各数値が出現する回数をカウントします。

並べ替えをカウントする例 (疑似コード構文で):

Counting-sort(A, n):
  let B = [0...n] = [0]
  for x in A:
    B[x] = B[x] + 1
  let C = [] // an empty list
  for i in 0...n:
    for j in 0...B[i]: // add each number 0..n the number of times it appeared in A
      C.append(i)
  return C
于 2013-04-04T10:45:38.953 に答える
0

ここでバケットソートを読むと、バケットのサイズが1のバケットソートのように見えます。

バケットソートでは、要素をバケットに入れた後、各バケットをソートします。

ただし、あなたの場合、バケット サイズは 1 であるため、この手順は必要ありません。バケット サイズが 1 で、配列に既にマージされているため、バケットのマージも必要ありません。

于 2013-04-04T10:36:16.183 に答える
0

私はあなたがそこに鳩の穴のようなものを持っていると思います

于 2013-04-04T10:47:58.493 に答える