n 個のレコードに 1 から k の範囲のキーがあるとします。
- レコードを O(n+k) 時間でソートするアルゴリズムを書きます。
- 入力配列の外側で O(k) ストレージを使用できます。
- あなたのアルゴリズムは安定していますか？
カウントソートを使用すると、O（n + k）時間で実行でき、安定していますが、適切ではありません。
k=2 の場合はその場で実行できますが、安定していません (k=0 と k=1 の配列のインデックスを維持するために 2 つの変数を使用します)
。
質問する
8407 次
4 に答える
11
まず、カウントソートの仕組みを再ハッシュしましょう。
- ソートする配列内にすべてのキーが存在する頻度を数えます。これらのカウントは size の配列に書き込まれます
k。 - キー数の部分和を計算します。これにより、ソートされた配列内の等しいキーのすべてのビンの開始位置が得られます。
- 配列内のアイテムを最終位置に移動し、すべてのアイテムに対応するビンの開始位置をインクリメントします。
ここでの問題は、最終ステップをインプレースで実行する方法です。インプレース順列の標準的なアプローチは、最初の要素を選択し、正しい位置にある要素と交換することです。このステップは、最初の位置に属する要素にヒットするまで (サイクルが完了するまで) スワップされた要素で繰り返されます。次に、配列全体が処理されるまで、2 番目、3 番目などの位置の要素に対して手順全体が繰り返されます。
並べ替えのカウントの問題は、最終的な位置がすぐに利用可能ではなく、最終的なループですべてのビンの開始位置をインクリメントすることによって計算されることです。要素の開始位置を 2 回インクリメントしないようにするために、特定の位置にある要素が既にそこに移動されているかどうかを判断する方法を見つける必要があります。これは、すべてのビンの元の開始位置を追跡することで実行できます。要素が元の開始位置とビンの次の要素の位置の間にある場合、その要素は既に触れられています。
これは C99 で実行され、追加のストレージとしてO(n+k)2 つのサイズの配列のみを必要とする実装です。k最終順列ステップは安定していません。
#include <stdlib.h>
void in_place_counting_sort(int *a, int n, int k)
{
int *start = (int *)calloc(k + 1, sizeof(int));
int *end = (int *)malloc(k * sizeof(int));
// Count.
for (int i = 0; i < n; ++i) {
++start[a[i]];
}
// Compute partial sums.
for (int bin = 0, sum = 0; bin < k; ++bin) {
int tmp = start[bin];
start[bin] = sum;
end[bin] = sum;
sum += tmp;
}
start[k] = n;
// Move elements.
for (int i = 0, cur_bin = 0; i < n; ++i) {
while (i >= start[cur_bin+1]) { ++cur_bin; }
if (i < end[cur_bin]) {
// Element has already been processed.
continue;
}
int bin = a[i];
while (bin != cur_bin) {
int j = end[bin]++;
// Swap bin and a[j]
int tmp = a[j];
a[j] = bin;
bin = tmp;
}
a[i] = bin;
++end[cur_bin];
}
free(start);
free(end);
}
編集:kこれは、Mohit Bhura のアプローチに基づいて、サイズの配列を 1 つだけ使用する別のバージョンです。
#include <stdlib.h>
void in_place_counting_sort(int *a, int n, int k)
{
int *counts = (int *)calloc(k, sizeof(int));
// Count.
for (int i = 0; i < n; ++i) {
++counts[a[i]];
}
// Compute partial sums.
for (int val = 0, sum = 0; val < k; ++val) {
int tmp = counts[val];
counts[val] = sum;
sum += tmp;
}
// Move elements.
for (int i = n - 1; i >= 0; --i) {
int val = a[i];
int j = counts[val];
if (j < i) {
// Process a fresh cycle. Since the index 'i' moves
// downward and the counts move upward, it is
// guaranteed that a value is never moved twice.
do {
++counts[val];
// Swap val and a[j].
int tmp = val;
val = a[j];
a[j] = tmp;
j = counts[val];
} while (j < i);
// Move final value into place.
a[i] = val;
}
}
free(counts);
}
于 2013-03-30T15:04:42.533 に答える
4
O(n+k) 時間で実行され、サイズ k の余分な配列を 1 つだけ使用するコードを次に示します (サイズ n のメイン配列とは別に)。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(int argc, char const *argv[])
{
int n = atoi(argv[1]);
int k = atoi(argv[2]);
printf("%d\t%d",n,k);
int *a,*c;
int num,index,tmp,i;
a = (int*)malloc(n*sizeof(int));
c = (int*)calloc(k,sizeof(int));
srand(time(NULL));
for(i=0;i<n;i++)
{
num = (rand() % (k));
a[i] = num;
c[num]++;
}
printf("\n\nArray is : \n");
for(i=0;i<n;i++)
{
printf("\t%d",a[i]);
if(i%8==7)
printf("\n");
}
printf("\n\nCount Array is : \n");
for(i=0;i<k;i++)
{
printf("\t%d(%d)",c[i],i);
if(i%8==7)
printf("\n");
}
//Indexing count Array
c[0]--;
for(i=1;i<k;i++)
{
c[i] = c[i-1] + c[i];
}
printf("\n\nCount Array After Indexing is : \n");
for(i=0;i<k;i++)
{
printf("\t%d(%d)",c[i],i);
if(i%8==7)
printf("\n");
}
// Swapping Elements in Array
for(i=0;i<n;i++)
{
index = c[a[i]];
//printf("\na[%d] = %d, going to position %d",i,a[i],index);
c[a[i]]--;
if(index > i)
{
tmp = a[i];
a[i] = a[index];
a[index] = tmp;
i--;
}
}
printf("\n\n\tFinal Sorted Array is : \n\n");
for(i=0;i<n;i++)
{
printf("\t%d",a[i]);
if(i%8==7)
printf("\n");
}
printf("\n\n");
return 0;
}
このアルゴリズムでさえ安定していません。すべての要素が逆順になっています。
Ps : キーは 0 から (k-1) の範囲にあります
于 2014-08-27T06:51:31.553 に答える
0
整数値シーケンスの例。ソートが不安定です。Mohit が提供する回答ほど簡潔ではありませんが、正しいビンに既にある要素をスキップすることで (時間は漸近的に同じです)、わずかに高速です (k << n の一般的なケースの場合)。実際には、ループがよりタイトでシンプルな Mohit のソートを好みます。
def sort_inplace(seq):
min_ = min(seq)
max_ = max(seq)
k = max_ - min_ + 1
stop = [0] * k
for i in seq:
stop[i - min_] += 1
for j in range(1, k):
stop[j] += stop[j - 1]
insert = [0] + stop[:k - 1]
for j in range(k):
while insert[j] < stop[j] and seq[insert[j]] == j + min_:
insert[j] += 1
tmp = None
for j in range(k):
while insert[j] < stop[j]:
tmp, seq[insert[j]] = seq[insert[j]], tmp
while tmp is not None:
bin_ = tmp - min_
tmp, seq[insert[bin_]] = seq[insert[bin_]], tmp
while insert[bin_] < stop[bin_] and seq[insert[bin_]] == bin_ + min_:
insert[bin_] += 1
よりタイトなループを使用しますが、既に再配置された要素をスキップします:
def dave_sort(seq):
min_ = min(seq)
max_ = max(seq)
k = max_ - min_ + 1
stop = [0] * k
for i in seq:
stop[i - min_] += 1
for i in range(1, k):
stop[i] += stop[i-1]
insert = [0] + stop[:k - 1]
for meh in range(0, k - 1):
i = insert[meh]
while i < stop[meh]:
bin_ = seq[i] - min_
if insert[bin_] > i:
tmp = seq[insert[bin_]]
seq[insert[bin_]] = seq[i]
seq[i] = tmp
insert[bin_] += 1
else:
i += 1
編集: 並べ替えの安定性への影響を検証するための余分なビットを使用した Python での Mohit のアプローチ。
from collections import namedtuple
from random import randrange
KV = namedtuple("KV", "k v")
def mohit_sort(seq, key):
f = lambda v: getattr(v, key)
keys = map(f, seq)
min_ = min(keys)
max_ = max(keys)
k = max_ - min_ + 1
insert = [0] * k
for i in keys:
insert[i - min_] += 1
insert[0] -= 1
for i in range(1, k):
insert[i] += insert[i-1]
i = 0
n = len(seq)
while i < n:
bin_ = f(seq[i])
if insert[bin_] > i:
seq[i], seq[insert[bin_]] = seq[insert[bin_]], seq[i]
i -= 1
insert[bin_] -= 1
i += 1
def test(n, k):
seq = []
vals = [0] * k
for _ in range(n):
key = randrange(k)
seq.append(KV(key, vals[key]))
vals[key] += 1
print(seq)
mohit_sort(seq, "k")
print(seq)
if __name__ == "__main__":
test(20, 3)
于 2015-11-03T06:47:38.717 に答える