基数ソート
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[C.S.R. Wiki トップページ]]
*基数ソート [#wdbfbebe]
基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)...
**アルゴリズム [#dc828555]
(1)入力の数列は、いくつかのキーに分類する。例えば、3桁の...
(2)それぞれのキーについて、下位のキーからソートする。~
~
たとえば、~
170, 45, 75, 90, 2, 24, 802, 66
という数列を1の位についてソートすると、~
170, 90, 2, 802, 24, 45, 75, 66
となる。さらに、10の位についてソートすると、~
2, 802, 24, 45, 66, 170, 75, 90
となる。最後に、100の位についてソートすると、~
2, 24, 45, 66, 75, 90, 170, 802
となり、ソートが完了する。~
~
(Wikipedia-基数ソートより抜粋)
~
**プログラム [#m66e7da7]
//a[]:整列前配列,work[]:作業領域,n:要素数,bit:基数=2^bit
void radixsort(unsigned long long a[], unsigned long lon...
{
int i, shift, range = 1 << bit;
int *count;
unsigned long long mask = range - 1;
unsigned long long *a_save = a, *tmp;
count = (int *)malloc(range * sizeof(int));
for(shift = 0; 0xffffffffffffffff > pow(2.0, bit*shift...
for(i = 0; i < range; i++) count[i] = 0;
for(i = 0; i < n; i++) count[(a_save[i] >> (bit*shif...
for(i = 1; i < range; i++) count[i] += count[i - 1];
for(i = n - 1; i >= 0; i--) work[--count[(a_save[i] ...
tmp = work;
work = a_save;
a_save = tmp;
}
for( i = 0 ; i < n ; i ++)a[i] = a_save[i];
free(count);
}
IEEEフォーマットの場合、double a,b が a > b > 0 であれば ...
**実行速度 [#ybd6fac1]
bit=5, n=20000000で要素がすべてランダムに与えられている場...
要素数が50以下で挿入ソートに切り替えるクイックソートでは ...
標準C++ライブラリ <algorithm> の std::sort では1.92701(s)~
~
終了行:
[[C.S.R. Wiki トップページ]]
*基数ソート [#wdbfbebe]
基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)...
**アルゴリズム [#dc828555]
(1)入力の数列は、いくつかのキーに分類する。例えば、3桁の...
(2)それぞれのキーについて、下位のキーからソートする。~
~
たとえば、~
170, 45, 75, 90, 2, 24, 802, 66
という数列を1の位についてソートすると、~
170, 90, 2, 802, 24, 45, 75, 66
となる。さらに、10の位についてソートすると、~
2, 802, 24, 45, 66, 170, 75, 90
となる。最後に、100の位についてソートすると、~
2, 24, 45, 66, 75, 90, 170, 802
となり、ソートが完了する。~
~
(Wikipedia-基数ソートより抜粋)
~
**プログラム [#m66e7da7]
//a[]:整列前配列,work[]:作業領域,n:要素数,bit:基数=2^bit
void radixsort(unsigned long long a[], unsigned long lon...
{
int i, shift, range = 1 << bit;
int *count;
unsigned long long mask = range - 1;
unsigned long long *a_save = a, *tmp;
count = (int *)malloc(range * sizeof(int));
for(shift = 0; 0xffffffffffffffff > pow(2.0, bit*shift...
for(i = 0; i < range; i++) count[i] = 0;
for(i = 0; i < n; i++) count[(a_save[i] >> (bit*shif...
for(i = 1; i < range; i++) count[i] += count[i - 1];
for(i = n - 1; i >= 0; i--) work[--count[(a_save[i] ...
tmp = work;
work = a_save;
a_save = tmp;
}
for( i = 0 ; i < n ; i ++)a[i] = a_save[i];
free(count);
}
IEEEフォーマットの場合、double a,b が a > b > 0 であれば ...
**実行速度 [#ybd6fac1]
bit=5, n=20000000で要素がすべてランダムに与えられている場...
要素数が50以下で挿入ソートに切り替えるクイックソートでは ...
標準C++ライブラリ <algorithm> の std::sort では1.92701(s)~
~
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
