C言語の基本的な並べ替えアルゴリズムのバレル式の並べ替えの例
本明細書の例は、C言語の基本的な順序付けアルゴリズムのバレル式の順序付けを説明する。皆さんに参考にしてあげます。具体的には以下の通りです。
バレルの並べ替えは、n個の整体要素を有する配列a[n]であり、i、0<=a[i]<=mの特別な並べ替えアルゴリズムである。
n==m,n!mそれぞれ処理します。コードを書く時に注意したいのは、i番目ではなく、i番目の元素にアクセスするのです。
バレルの並べ替えは、n個の整体要素を有する配列a[n]であり、i、0<=a[i]<=mの特別な並べ替えアルゴリズムである。
n==m,n!mそれぞれ処理します。コードを書く時に注意したいのは、i番目ではなく、i番目の元素にアクセスするのです。
/************************************************************************************/
/* Bucket_Sort.h */
/* : n a[0],a[1],…,a[n-1] , 0 <= a[i] <= m, i */
/* : O(m+n), O(m) */
/* n=m , O(N), O(1) */
/************************************************************************************/
#include <vector>
/*m != n */
void Bucket_Sort_m(int *a, int n, int m)
{
std::vector<int> temp(m,0);
int i;
for(i = 0; i != n; ++i) // a[]
++temp[a[i]-1]; // , 1, 0
i = 0;
for(int j = 1; j <= m; ++j) // temp
if(temp[j-1]) a[i++] = j;
temp.clear();
}
/* m == n */
/* a[i-1] = i */
void Bucket_Sort(int *a,int n)
{
for(int i = 1; i <= n; ++i)
{
while(a[i-1] != i)
{
int temp = a[a[i-1]-1];
a[a[i-1]-1] = a[i-1];
a[i-1] = temp;
}
/* : a[i] i , i-1 */
/*while(a[i] != i)
{
int temp = a[a[i]];
a[a[i]] = a[i];
a[i] = temp;
}
*/
}
}
ここで述べたように、皆さんのC言語プログラムの設計に役に立ちます。