c - 文字列の配列をアルファベット順に並べ替える方法 (大文字と小文字を区別する、非標準の照合)

Question

一部の文字列を並べ替えるには AC 言語コードが必要です。大文字と小文字を区別する必要があり、大文字と小文字の同じ文字の場合、小文字が最初に来る必要があります。たとえば、次の文字列の並べ替えの結果:

eggs
bacon
cheese
Milk
spinach
potatoes
milk
spaghetti

次のようにする必要があります。

bacon
cheese
eggs
milk
Milk
potatoes
spaghetti
spinach

コードを書きましたが、得られる結果は次のとおりです。

Milk
bacon
cheese
eggs
milk
potatoes
spaghetti
spinach

これを改善する方法がわからず、たくさん検索しました。誰でもこれで私を助けることができますか？

#include <stdio.h>
#include <string.h>

int main(){
    char c;
    char name[20][10], temp[10];
    int count_name = 0;
    int name_index = 0;
    int i, j;

    while ((c = getchar()) != EOF){
        if (c == 10){
            name[count_name][name_index] = '\0';
            count_name++;
            name_index = 0;
        } else {
            name[count_name][name_index] = c;
            name_index++;
        }
    }

    for(i=0; i < count_name-1 ; i++){
        for(j=i+1; j< count_name; j++)
        {
            if(strcmp(name[i],name[j]) > 0)
            {
                strcpy(temp,name[i]);
                strcpy(name[i],name[j]);
                strcpy(name[j],temp);
            }
        }
    }

    for (i = 0; i < count_name; i++){
        printf("%s\n", name[i]);
    }
}

Answer 1

ソート用のカスタム比較関数を作成できます。

まず、デフォルトのstrcmpソート順を見てください。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

const char *tgt[]={
    "bacon", "Bacon", "mIlk", "Milk", "spinach", "MILK", "milk", "eggs"
};
int tgt_size=8;

static int cmp(const void *p1, const void *p2){
    return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int main(int argc, char *argv[]) {
    printf("Before sort:\n\t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    qsort(tgt, tgt_size, sizeof(char *), cmp);

    printf("\nAfter sort:\n\t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    return 0;
}

strcmpASCII 文字コードで並べ替えます。つまり、すべて大文字の AZ が小文字の単語の前に来るように並べ替えますA-Z。a-z

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    Bacon MILK Milk bacon eggs mIlk milk spinach 

cmp大文字と小文字を区別しない独自の比較関数を書きますqsort。それは次のようになります。

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == '\0')
            return 0;
    return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);
} 

また、必ず次のように変更cmpしてください。

static int cmp(const void *p1, const void *p2){
    return mycmp(* (char * const *) p1, * (char * const *) p2);
}

大文字と小文字を無視するバージョンが出力されるようになりました:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs Milk MILK milk mIlk spinach 

これは、POSIX 関数strcasecmpで得られる出力と同じです。

この関数mycmpは、最初に正規の順序で辞書式に比較し[a|A]-[z|Z]ます。これは、文字の単語が一緒になることを意味しますがbacon, Bacon、可能性はBacon, bacon. これは、qsort が安定ソートではなく、'Bacon' が 'bacon' と等しいためです。

ここで必要なのは、大文字と小文字を無視して比較が 0 の場合 (つまり、'MILK' と 'milk' のような同じ単語)、大文字と小文字を含めて比較し、順序を逆にすることです。

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;
    int sccmp=1;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == '\0')
            sccmp = 0;
    if (sccmp) return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);

    for (; *a == *b; a++, b++)
        if (*a == '\0')
            return 0;
    return ((*a < *b) ? +1 : -1);
}

最終版のプリント:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs milk mIlk Milk MILK spinach 

残念ながら、このアプローチは UNICODE では扱いにくくなります。複雑な並べ替えの場合は、マッピングまたは安定した並べ替えを使用したマルチステップ 並べ替えを使用することを検討してください。

複雑で位置を認識するアルファベット順の照合については、Unicode 照合を検討してください。例として、異なる場所では、文字のアルファベット順が異なります。

Swedish                      z < ö
                             y == w
German                       ö < z
Danish                       Z < Å
Lithuanian                   i < y < k
Tr German                    ä == æ
Tr Spanish                   c < ch < d   
German Dictionary Sort:      of < öf
German Phonebook Sort:       öf < of

これらの区別のデフォルト値は、UNICODE 照合と文字列比較のデフォルト マッピングを提供するデフォルト Unicode 照合要素テーブル ( DUCET ) に取り込まれます。デフォルトを変更して、辞書の並べ替えと電話帳の並べ替え、異なる場所、または大文字と小文字の異なる処理を区別できます。個々の場所のバリエーションは、Unicode Common Locale Data Repository ( CLDR ) で積極的に追跡されています。

複数レベルの並べ替えの推奨事項は次のとおりです。

Level   Description           Examples
L1      Base characters       role < roles < rule
L2      Accents               role < rôle < roles
L3      Case/Variants         role < Role < rôle
L4      Punctuation           role < “role” < Role
Ln      Identical             role < ro□le < “role”

広く使用されている Unicode 照合の実装は、ICU ライブラリにあります。いくつかの例のデフォルトの DUCET 照合は次のようになります。

b < B < bad < Bad < bäd
c < C < cote < coté < côte < côté 

ICU ライブラリを探索し、 ICU Explorerで場所とターゲットを変更できます

笑いのために独自のバージョンの DUCET を実装したい場合は、このPython スクリプトで使用されている一般的な方法に従うことができます。圧倒的ではありませんが、些細なことではありません。

Answer 2

OP コードの鍵は、関数を使用strcmp()して 2 つの文字列を比較することです。
そこで、次のように、この標準関数を別の関数に置き換えることから始めます。

  // We assume that the collating sequence satisfies the following rules:
  // 'A' < 'B' < 'C' < ...
  // 'a' < 'b' < 'c' < ...
  // We don't make any other assumptions.

  #include <ctype.h>      
  int my_strcmp(const char * s1, const char * s2)
  {
      const char *p1 = s1, *p2 = s2;
      while(*p1 == *p2 && *p1 != '\0' && *p2 != '\0')
          p1++, p2++;  /* keep searching... */

      if (*p1 == *p2)
         return 0;
      if (*p1 == '\0')
         return -1;
      if (*p2 == '\0')
         return +1;

      char c1 = tolower(*p1),      c2 = tolower(*p2);
      int  u1 = isupper(*p1) != 0, u2 = isupper(*p2) != 0;
      if (c1 != c2)
        return c1 - c2;  // <<--- Alphabetical order assumption is used here 
      if (c1 == c2)
        return u1 - u2;
  }

最後の行は次のように圧縮できます。

     return (c1 != c2)? c1 - c2: u1 - u2;

ここで、を置き換えることで、望ましい結果が得 strcmp()られます。my_strcmp()

ソート アルゴリズムでは、次の 3 つの主な側面を別々に考えることをお勧めします。

• 比較機能。
• 使用する抽象ソート アルゴリズム。
• 2 つの項目を交換する必要がある場合、そのデータは配列内で「移動」されます。

これらの側面は、個別に最適化できます。
したがって、たとえば、比較関数が十分に確立されたら、次の最適化ステップは、ソート アルゴリズムのdouble を、より効率的なもの ( quicksortなど) に置き換えることです。
特に、qsort()標準ライブラリの関数はその<stdlib.h>ようなアルゴリズムを提供するため、プログラミングを気にする必要はありません。
最後に、配列情報を格納するために使用する戦略は、パフォーマンスに影響を与える可能性があります。
「char の配列の配列」の代わりに「char へのポインターの配列」のような文字列を格納する方が効率的です。これは、ポインターの交換は 2 つの char の配列全体を交換するよりも高速であるためです。

ポインターの配列

追加の注意:最初の 3 つif()の は実際には冗長です。これは、次の文のロジックが*p1or*p2が 0 の場合に望ましい結果を暗示しているためです。ただし、これらif()の を保持することで、コードが読みやすくなります。

Answer 3

ここで、私が正しければ、次のように説明するものが必要です。

大文字と小文字を区別しないソートで、タイの下ではタイブレーカー条件「小文字が最初」が使用されます。

つまり、次のようになります。

1. earlier_letter_in_the_alphabet < later_letter_in_the_alphabetケースを無視する

2. lowercase < uppercase

3. shorter_word < wider_word
   • これは言及されていませんでした。辞書の順序から借りました。
   • '\0'比較で可能な限り低い値を取るだけで利用できます

ステップ 2 は、1 で何も区別されなかった場合にのみ実行されます。ステップ 3 はすでに 1 でチェックされています。これらはすべて文字ごとに行われます。つまり、文字列全体がタイになったときだけでなく、対応する文字がタイになったらすぐに 2 に切り替える必要があります。

---

これが正しかったと仮定すると、次に行う必要があるのは、任意の 2 つの文字列についてこの比較を行う関数を作成することだけです。

#include <ctype.h>  // for tolower and islower

int my_character_compare(const char a, const char b)
{
    int my_result;

    my_result = tolower(a) - tolower(b);
    // unless it is zero, my_result is definitely the result here
    // Note: if any one of them was 0, result will also properly favour that one


    if (my_result == 0 && a != b)
    // if (could not be distinguished with #1, but are different)
    {
        // means that they are case-insensitively same
        // but different...
        // means that one of them are lowercase, the other one is upper
        if (islower(a))
            return -1;  // favour a
        else
            return 1;   // favour b
    }


    // regardless if zero or not, my_result is definitely just the result
    return my_result;
}

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    my_result = my_character_compare(*a, *b);
    // unless it is zero, my_result is definitely the result here

    while (my_result == 0 && *a != 0)
    // current characters deemed to be same
    // if they are not both just 0 we will have to check the next ones
    {
        my_result = my_character_compare(*++a, *++b);
    }

    // whatever the my_result has been:
    //   whether it became != zero on the way and broke out of the loop
    //   or it is still zero, but we have also reached the end of the road/strings
    return my_result;
}

慣例/ルールにより、比較関数は、最初のパラメーターを優先する場合は負の値を返し、2 番目のパラメーターを優先する場合は負の値を返し、それらを区別できない場合はゼロを返す必要があります。を使用する方法で既に知っている可能性が高い追加情報ですstrcmp。

以上です！strcmpコード内でmy_string_compareこれをここに置き換え、作成したこれらの定義を一番上に配置すると、正しい結果が得られるはずです。実際、問題の入力例に対して期待される結果が得られます。

もちろん、定義を短くすることもできますが、何が起こっているのかを理解しやすくするために、定義を長くしました。たとえば、すべてを次のように煮詰めることができます。

#include <ctype.h>

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    while (*a || *b)
    {
        if ((my_result = tolower(*a) - tolower(*b)))
            return my_result;
        if (*a != *b)
            return (islower(*a)) ? -1 : 1;
        a++;
        b++;
    }

    return 0;
}

他のものと本質的に同じことを行います。好きなものを使用できます。またはさらに良いことに、1つ書いてください。

Answer 4

私はこの議論に遅れており、白鳥になって素晴らしい賞を獲得することを特に期待していませんが、最初に検討したイディオムを使用した解決策が見られなかったので、参加したいと思いました.

問題の仕様を読んで最初に考えたのは、基本的に@jxhの照合テーブルの概念の使用で見つけた、何らかの形式のカスタム照合シーケンスでした。私は大文字と小文字を区別しないことを中心的な概念とは考えていません。ただの奇妙な順序付けです。

したがって、純粋に代替実装として次のコードを提供します。これは glibc に固有のものです - qsort_r(3)が使用されます - しかし、より軽量なアプローチのように感じられ、実行時に多くの照合シーケンスをサポートします。しかし、それは軽くテストされており、さまざまな弱点を見落としている可能性が非常に高い. その中でも、私は Unicode やワイド文字の世界全般に特に注意を払っていませんでした。また、負の配列添え字を避けるために unsigned char にキャストすることは疑わしいと感じています。

#include <stdio.h>
#include <limits.h>

/*
 * Initialize an index array associated with the collating
 * sequence in co. The affected array can subsequently be
 * passed in as the final client data pointer into qsort_r
 * to be used by collating_compare below.
 */
int
collating_init(const char *co, int *cv, size_t n)
{
    const unsigned char *uco = (const unsigned char *) co;
    const unsigned char *s;
    size_t i;

    if (n <= UCHAR_MAX) {
        return -1;
    }
    for (i = 0; i < n; i++) {
        /* default for chars not named in the sequence */
        cv[i] = UCHAR_MAX;
    }
    for (s = uco; *s; s++) {
        /*
         * the "collating value" for a character's own
         * character code is its ordinal (starting from
         * zero) in the collating sequence. I.e., we
         * compare the values of cv['a'] and cv['A'] -
         * rather than 'a' and 'A' - to determine order.
         */
        cv[*s] = (s - uco);
    }

    return 0;
}

static int
_collating_compare(const char *str1, const char *str2, int *ip)
{
    const unsigned char *s1 = (const unsigned char *) str1;
    const unsigned char *s2 = (const unsigned char *) str2;

    while (*s1 != '\0' && *s2 != '\0') {
        int cv1 = ip[*s1++];
        int cv2 = ip[*s2++];

        if (cv1 < cv2) return -1;
        if (cv1 > cv2) return 1;
    }

    if (*s1 == '\0' && *s2 == '\0') {
        return 0;
    } else {
        return *s1 == '\0' ? -1 : 1;
    }
}

int
collating_compare(const void *v1, const void *v2, void *p)
{
    return _collating_compare(*(const char **) v1,
                              *(const char **) v2,
                              (int *) p);
}

前のものは、別のモジュールまたはライブラリに配置できるコードに近いですが、独自のヘッダー ファイル (またはヘッダー ファイルのエントリ) がありません。私自身のテストでは、上記と以下のコードを custom_collat​​e_sort.c という名前のファイルに連結し、

gcc -DMAIN_TEST -Wall -o custom_collate_sort custom_collate_sort.c

...コンパイルします。

#if defined(MAIN_TEST)

/* qsort_r is a GNU-ey thing... */

#define __USE_GNU
#include <stdlib.h>
#include <string.h>

#define NELEM(x) (sizeof x / sizeof 0[x])

static int
cmp(const void *v1, const void *v2)
{
    return strcmp(*(const char **) v1, *(const char **) v2);
}

static int
casecmp(const void *v1, const void *v2)
{
    return strcasecmp(*(const char **) v1, *(const char **) v2);
}

int
main(int ac, char *av[])
{
    size_t i;

    int cval[256], ret;
    int cval_rev[256], rret;

    char *tosort[] = {
        "cheeSE", "eggs", "Milk", "potatoes", "cheese", "spaghetti",
        "eggs", "milk", "spinach", "bacon", "egg", "apple", "PEAR",
        "pea", "berry"
    };

    ret = collating_init("aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVxXyYzZ",
                         cval, NELEM(cval));

    rret = collating_init("ZzYyXxVvUuTtSsRrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa",
                          cval_rev, NELEM(cval_rev));

    if (ret == -1 || rret == -1) {
        fputs("collating value array must accomodate an index of UCHAR_MAX\n", stderr);
        return 1;
    }

    puts("Unsorted:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], cmp);

    puts("Sorted w/ strcmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], casecmp);

    puts("Sorted w/ strcasecmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval);

    puts("Sorted w/ collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval_rev);

    puts("Sorted w/ reversed collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    return 0;
}

#endif /* MAIN_TEST */

Answer 5

プログラムに必要な標準ヘッダー ファイル:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

主なプログラムはここから始まります:

//Global Variables Required
//=========
const char *tgt[]={"bacon", "Bacon", "mIlk", 
        "Milk", "spinach", "MILK", "milk", "eggs"};    //Array for sorting
int tgt_size=8;                                        //Total Number of Records
int     SortLookupTable[128];                          //Custom sorting table
typedef int      cmp_t (const void *, const void *);




int main(int argc, char *argv[]) {
    printf("Before sort:\n\n");
    int n=0;
    for(n=0; n<tgt_size; n++)
        printf("%s\n", tgt[n]);

    CreateSortTable();

    myQsort(tgt, tgt_size, sizeof(char *), &compare);
    printf("\n\n====\n\n");
    for(n=0; n<tgt_size; n++)
        printf("%s\n", tgt[n]);

    return 0;
}

必要に応じてカスタムの並べ替えテーブル:

void CreateSortTable(void){
    int     i;
    for (i = 0; i < 128; i++){
        SortLookupTable[i] = 0;
    }
    char *s;
    s=(char *)malloc(64);
    memset(s, 0, 64);
    strcpy(s, "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");

    i=1;
    for (; *s; s++){
        SortLookupTable[(int) ((unsigned char) *s)]=i;
        i++;
    }
}

クイックソートアルゴリズム、提供されている標準ライブラリを使用することもできます:

//Some important Definations required by Quick Sort
=======
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
    es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

#define swap(a, b)                          \
    if (swaptype == 0) {                    \
        long t = *(long *)(a);              \
        *(long *)(a) = *(long *)(b);        \
        *(long *)(b) = t;                   \
    } else                                  \
        swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n)    if ((n) > 0) swapfunc(a, b, n, swaptype)


#define swapcode(TYPE, parmi, parmj, n) {       \
    long i = (n) / sizeof (TYPE);               \
    register TYPE *pi = (TYPE *) (parmi);       \
    register TYPE *pj = (TYPE *) (parmj);       \
    do {                                        \
        register TYPE   t = *pi;                \
        *pi++ = *pj;                            \
        *pj++ = t;                              \
        } while (--i > 0);                      \
}

#define min(a, b)   (a) < (b) ? a : b


//Other important function
void swapfunc(char *a, char *b, int n, int swaptype){
    if(swaptype <= 1)
        swapcode(long, a, b, n)
    else
        swapcode(char, a, b, n)
}

char * med3(char *a, char *b, char *c, cmp_t *cmp){
    if ( cmp(a, b) < 0){
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){

                return c;
            }else{
                return a;
            }
        }
    }else{
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){
                return a;
            }else{
                return c;
            }
        }
    }
}

//Custom Quick Sort

void myQsort(void *a, unsigned int n, unsigned int es, cmp_t *cmp){
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    int d, r, swaptype, swap_cnt;

loop:   SWAPINIT(a, es);
    swap_cnt = 0;
    if (n < 7) {
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es){
                swap(pl, pl - es);
            }
        return;
    }
    pm = (char *)a + (n / 2) * es;
    if (n > 7) {
        pl = a;
        pn = (char *)a + (n - 1) * es;
        if (n > 40) {
            d = (n / 8) * es;
            pl = med3(pl, pl + d, pl + 2 * d, cmp);
            pm = med3(pm - d, pm, pm + d, cmp);
            pn = med3(pn - 2 * d, pn - d, pn, cmp);
        }
        pm = med3(pl, pm, pn, cmp);
    }
    swap(a, pm);
    pa = pb = (char *)a + es;

    pc = pd = (char *)a + (n - 1) * es;
    for (;;) {
        while (pb <= pc && (r = cmp(pb, a)) <= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pa, pb);
                pa += es;
            }
            pb += es;
        }
        while (pb <= pc && (r = cmp(pc, a)) >= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pc, pd);
                pd -= es;
            }
            pc -= es;
        }
        if (pb > pc)
            break;
        swap(pb, pc);
        swap_cnt = 1;
        pb += es;
        pc -= es;
    }
    if (swap_cnt == 0) {  /* Switch to insertion sort */
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
                 pl -= es)
                swap(pl, pl - es);
        return;
    }

    pn = (char *)a + n * es;
    r = min(pa - (char *)a, pb - pa);
    vecswap(a, pb - r, r);
    r = min(pd - pc, pn - pd - es);
    vecswap(pb, pn - r, r);
    if ((r = pb - pa) > es)
        myQsort(a, r / es, es, cmp);
    if ((r = pd - pc) > es) {
        /* Iterate rather than recurse to save stack space */
        a = pn - r;
        n = r / es;
        goto loop;
    }
}

最も重要な機能は次の 2 つです。

unsigned char Change(char a){
    return (unsigned char ) SortLookupTable[(int)a];
}


int compare (const void *a, const void *b){
    char *s1= *(char **)a;
    char *s2= *(char **)b;
    int ret, len, i;
    ret=0;

    if (strlen((void*)s1) > strlen((void*)s2)){
        len=strlen((void*)s1);
    }else{
        len=strlen((void*)s2) ;
    }

    for(i=0; i<len; i++){
        if ( s1[i] != s2[i]){
            if ( Change(s1[i]) < Change(s2[i]) ){
                ret=0;
                break;
            }else{
                ret=1;
                break;
            }
        }
    }

    return ret;
}