Cで文字の配列をアルファベット順にソートする、シンプルでわかりやすいアルゴリズムを探しています.
7 に答える
C の文字には数値がたまたま順番に並んでいるので、文字を整数のように扱うだけです。C 標準ライブラリには「qsort」関数が含まれています。それを使用してください(man qsort
Linuxのようなシステムで)。単純化するために大文字を小文字に変換する必要があるかもしれませんが、それは簡単なことです。クイックソート アルゴリズムを理解したい場合 (実際に使用するため、習得する必要があります)、Wikipediaを参照してください。
結果が人間を対象としている場合は、strcollを使用することをお勧めします。strcmpやstrcasecmpよりも低速ですが、英語以外の文字を考慮しています。使用する場合は、LC_COLLATEのロケールを設定することを忘れないでください。
setlocale(LC_COLLATE、 "");
qsort メソッドを使用します。
#include <stdlib.h>
int char_compare (const void * a, const void * b)
{
return *(const char *)a - *(const char *)b;
}
int main(){
const char char_array[] = { 'c', 'a', 'b' };
qsort (char_array, 3, sizeof(char), char_compare);
return 0;
}
あなたが本当にアルゴリズムを探しているのか、それとも問題を解決する方法を探しているのだろうか?後者の場合は、Cのqsortを使用します。
アルゴリズムが必要な場合は、非常に理解しやすいので、挿入ソートまたは選択ソートを選択してください。
最も簡単なソート アルゴリズムであるバブル ソートを試してみてください。
簡単?バブルソートを行います。
これはcharではなくjavaとintですが、簡単に適応できます...
int[] bubble(int a[])
{
for (int i = a.length; --i>=0; )
{
for (int j = 0; j<i; j++)
{
if (a[j] > a[j+1])
{
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
}
}
}
return(a);
}
これは非常に単純で、漸近的に最速です (N は配列のサイズです)。
const unsigned char in[N];
unsigned char out[N], *p=out;
size_t cnt[N]={0}, i, j;
for (i=0; i<COUNT; i++) cnt[in[i]]++;
for (i=0; i<256; i++) for (j=cnt[i]; j; j--) *p++=i;