C言語関係掲示板

過去ログ

No.924 クイックソートで辞書順

[戻る] [ホームページ]
No.11693

クイックソートで辞書順
投稿者---埼玉(2004/01/12 16:43:51)


下記のようなコードでクイックソートを使用しアルファベット表記の名前を辞書順に出力したいのですがうまく出力しません。(アルファベット順に並ばない)ご指摘願います。(Win XP/bcc)

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

  void quick_sort(char [][30],int,int);

  int main()
  {
    int i;
    char name[][30]={
      "Ka","Ao","Is","Wa","Ue",
      "Uet","On","Oga","Aok","Ka",
      "Kim","Kik","Kur","Ko","Sa",
      "Sai","Sag","Sas","Shi","Shis",
      "Shir","Suz","Su","Seg","Set",
      "Son","Tac","Tag","Too","Tsu",
      "Tom","Tod","Nak","Ni","Nem",
      "Nom","Ha","Hi","Ho","Ma",
      "Mi","Mu","Mo","Ya","Yo",
      "Yos","Yok","Wa","Wac","I"
    };

    quick_sort( name, 0, 49 );
      for( i=0; i<50; i++ ) printf(" %s \n",name[i]);

  return 0;
  }

  void quick_sort(char name[][30],int s,int e)
  {
    int i,j,x;
    char tmp[30]={0};

      if( s+1>=e ){
        if( strcmp(name[s],name[e]) >0 ) { 
          strcpy(tmp,name[s]);
          strcpy(name[s],name[e]); 
          strcpy(name[e],tmp);
        }
        return;
      }
      x=(s+e)/2;
      i=s; j=e;
      while(1){
        while( i<x ) i++;
          while( j>x ) j--;
            if( strcmp(name[i],name[j]) >0 ) break;
              strcpy(tmp,name[i]);
              strcpy(name[i],name[j]);
              strcpy(name[j],tmp);
              i++; j--;
      }
      quick_sort(name,s,j);
      quick_sort(name,i,e);
  }




No.11694

Re:クイックソートで辞書順
投稿者---かずま(2004/01/12 17:33:56)


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

void quick_sort(char *[], int, int);

int main()
{
    char *name[] = {
        "Ka",  "Ao",  "Is",  "Wa",  "Ue",
        "Uet", "On",  "Oga", "Aok", "Ka",
        "Kim", "Kik", "Kur", "Ko",  "Sa",
        "Sai", "Sag", "Sas", "Shi", "Shis",
        "Shir","Suz", "Su",  "Seg", "Set",
        "Son", "Tac", "Tag", "Too", "Tsu",
        "Tom", "Tod", "Nak", "Ni",  "Nem",
        "Nom", "Ha",  "Hi",  "Ho",  "Ma",
        "Mi",  "Mu",  "Mo",  "Ya",  "Yo",
        "Yos", "Yok", "Wa",  "Wac", "I"
    };
    const int size = sizeof name / sizeof *name;
    int i;

    quick_sort(name, 0, size-1);
    for (i = 0; i < size; i++) puts(name[i]);
    return 0;
}

void quick_sort(char *name[], int s, int e)
{
    int i, j, x;  char *t;

    if (s >= e) return;
    x = (s + e) / 2;
    for (i = s,  j = e; ; i++, j--) {
        while (strcmp(name[i], name[x]) < 0) i++;
        while (strcmp(name[j], name[x]) > 0) j--;
        if (i > j) break;
        t = name[i];  name[i] = name[j];  name[j] = t;
    }
    quick_sort(name, s, j);
    quick_sort(name, i, e);
}

----------------------------------------------------------------------
どうしても、二次元配列を使いたいのなら、

void quick_sort(char *[], int, int);
--> void quick_sort(char [][30], int, int);

char *name[] = {
--> char name[][30] = {

void quick_sort(char *name[], int s, int e)
--> void quick_sort(char name[][30], int s, int e)

int i, j, x;  char *t;
--> int i, j, x;  char t[30];

t = name[i];  name[i] = name[j];  name[j] = t;
--> strcpy(t, name[i]); strcpy(name[i], name[j]); strcpy(name[j], t);


No.11695

Re:クイックソートで辞書順
投稿者---埼玉(2004/01/12 20:00:35)


かずまさんありがとうございました。


No.11696

Re:クイックソートで辞書順
投稿者---かずま(2004/01/12 20:49:55)


> かずまさんありがとうございました。
プログラムが正しいとは限りません。検証はされたんでしょうか?

if (i > j) break; は間違いで、if (i >= j) break; かもしれないし、
そうなら、
    quick_sort(name, s, j);
    quick_sort(name, i, e);
も
    quick_sort(name, s, i-1);
    quick_sort(name, j+1, e);

にしないといけないのでは?


No.11697

Re:クイックソートで辞書順
投稿者---埼玉(2004/01/12 21:18:05)


> プログラムが正しいとは限りません。検証はされたんでしょうか?

下記両方のコードで検証したところ、50人中のうち後半の一部分が辞書順になっていないところがありました。どうしてでしょうか。(2次元配列で実施)

> if (i > j) break; は間違いで、if (i >= j) break; かもしれないし、
> quick_sort(name, s, j);
> quick_sort(name, i, e);
>
> quick_sort(name, s, i-1);
> quick_sort(name, j+1, e);



No.11818

Re:クイックソートで辞書順
投稿者---かずま(2004/01/15 19:02:28)


> 下記両方のコードで検証したところ、50人中のうち後半の一部分が辞書順に
> なっていないところがありました。どうしてでしょうか。

次のように修正します。
void quick_sort(char *name[], int s, int e)
{
    int i, j;  char *t, *x;

    if (s >= e) return;
    x = name[(s + e) / 2];
    for (i = s,  j = e; ; i++, j--) {
        while (strcmp(name[i], x) < 0) i++;
        while (strcmp(name[j], x) > 0) j--;
        if (i >= j) break;
        t = name[i];  name[i] = name[j];  name[j] = t;
    }
    quick_sort(name, s, i-1);
    quick_sort(name, j+1, e);
}


No.11819

Re:クイックソートで辞書順
投稿者---かずま(2004/01/15 19:25:34)


> 次のように修正します。

配列版だと、
    int i, j;  char t[30], x[30];

    strcpy(x, name[(s + e) / 2]);

ところで、どうして最近、ソートの質問が多いんでしょうか?
クイックソート、マージソート、選択ソート、......。

No.11828

Re:クイックソートで辞書順
投稿者---埼玉(2004/01/15 23:09:11)


かずまさんありがとうございました。