C言語関係掲示板

過去ログ

No８７４　元素記号構造体のクイックソート

[戻る]　[ホームページ]
No.11343
文字でのクイックソート
投稿者---ｋ王子(2003/12/20 16:16:14)


genso1.txtの内容の元素記号に関してクイックソートで昇順にしたいんですけど、私が作ったプログラムだと無限ループになってしまいます。
どうしたらよいのでしょうか？
私がつくったプログラム↓
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

typedef struct{
char kigou[10];
int number;
char english[30];
}Genso ;

void quick(Genso a[], int left, int right)
{
int pl = left;
int pr = right;
char *x = a[(pl+pr)/2].kigou;
int i;
int j;

do {
i=strcmp(a[pl].kigou, x);
j=strcmp(a[pr].kigou, x);
while (i < 0) pl++;
while (j > 0) pr--;
if (pl <= pr) {
swap(Genso, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);

if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}


int main(void)
{
char str[256];
FILE *infp;
FILE *outfp;
int i = 0;
Genso data[105];
int youso;

infp=fopen("genso1.txt", "r");
if(infp==NULL){
printf("Can not open file \n"); exit(1);
}
outfp=fopen("genso2.txt", "w");
if(outfp==NULL){
printf("Can not open file \n"); exit(1);
}

while ((fgets(str, sizeof(str), infp)) !=NULL){
sscanf(str, "%s %d %s", data[i].kigou, &data[i].number, data[i].english);
i++;
}
youso=i;
fclose(infp);

quick(data, 0, youso - 1);

for(i=0;i<youso;i++){
fprintf(outfp, "%s %d %s\n" , data[i].kigou, data[i].number, data[i].english);
}

fclose (outfp);
return(0);
}

genso1.txt(左から元素記号，原子番号，英語名の順）
H 1 Hydrogen
He 2 Helium
Li 3 Lithium
Be 4 Beryllium
B 5 Boron
C 6 Carbon
N 7 Nitrogen
O 8 Oxygen
F 9 Fluorine
Ne 10 Neon
Na 11 Sodium
Mg 12 Magnesium
Al 13 Aluminum
Si 14 Silicon
P 15 Phosphorus
S 16 Sulfur
Cl 17 Chlorine
Ar 18 Argon
K 19 Potassium
Ca 20 Calcium
Sc 21 Scandium
Ti 22 Titanium
V 23 Vanadium
Cr 24 Chromium
Mn 25 Manganese
Fe 26 Iron
Co 27 Cobalt
Ni 28 Nickel
Cu 29 Copper
Zn 30 Zinc
Ga 31 Gallium
Ge 32 Germanium
As 33 Arsenic
Se 34 Selenium
Br 35 Bromine
Kr 36 Krypton
Rb 37 Rubidium
Sr 38 Strontium
Y 39 Yttrium
Zr 40 Zirconium
Nb 41 Niobium
Mo 42 Molybdenum
Tc 43 Technetium
Ru 44 Ruthenium
Rh 45 Rhodium
Pd 46 Palladium
Ag 47 Silver
Cd 48 Cadmium
In 49 Indium
Sn 50 Tin
Sb 51 Antimony
Te 52 Tellurium
I 53 Iodine
Xe 54 Xenon
Cs 55 Cesium
Ba 56 Barium
La 57 Lanthanum
Ce 58 Cerium
Pr 59 Praseodymium
Nd 60 Neodymium
Pm 61 Promethium
Sm 62 Samarium
Eu 63 Europium
Gd 64 Gadolinium
Tb 65 Terbium
Dy 66 Dysprosium
Ho 67 Holmium
Er 68 Erbium
Tm 69 Thulium
Yb 70 Ytterbium
Lu 71 Lutetium
Hf 72 Hafnium
Ta 73 Tantalum
W 74 Tungsten
Re 75 Rhenium
Os 76 Osmium
Ir 77 Iridium
Pt 78 Platinum
Au 79 Gold
Hg 80 Mercury
Tl 81 Thallium
Pb 82 Lead
Bi 83 Bismuth
Po 84 Polonium
At 85 Astatine
Rn 86 Radon
Fr 87 Francium
Ra 88 Radium
Ac 89 Actinium
Th 90 Thorium
Pa 91 Protactinium
U 92 Uranium
Np 93 Neptunium
Pu 94 Plutonium
Am 95 Americium
Cm 96 Curium
Bk 97 Berkelium
Cf 98 Californium
Es 99 Einsteinium
Fm 100 Fermium
Md 101 Mendelevium
No 102 Nobelium
Lr 103 Lawrencium
No.11344
Re:文字でのクイックソート
投稿者---NykR(2003/12/20 16:25:11)


> while (i < 0) pl++;
> while (j > 0) pr--;

これ、一端中に入ると二度と出ることができませんよね。
No.11345
Re:文字でのクイックソート
投稿者---たか(2003/12/20 16:28:47)


まず気がついた所。

do {
i = strcmp(a[pl].kigou, x);
j = strcmp(a[pr].kigou, x);
while (i < 0) pl++;
while (j > 0) pr--;

iとj共にstrcmp()を一回実行するだけで、後は変化しませんので、ひょっ
としたらwhile文で無限ループに入るのではないかと思った次第です。
動作確認は今からします。
No.11346
Re:文字でのクイックソート
投稿者---たか(2003/12/20 16:35:13)


これで動きます。

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

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

typedef struct{
  char kigou[10];
  int number;
  char english[30];
} Genso;

void quick(Genso a[], int left, int right)
{
  int pl = left; 
  int pr = right; 
  char *x = a[(pl + pr) / 2].kigou; 

  do {
    while (strcmp(a[pl].kigou, x) < 0) pl++;
    while (strcmp(a[pr].kigou, x) > 0) pr--;
    if (pl <= pr) {
      swap(Genso, a[pl], a[pr]);
      pl++;
      pr--;
    }
  } while (pl <= pr);
  if (left < pr) quick(a, left, pr);
  if (pl < right) quick(a, pl, right);
}

int main(void)
{
  char str[256];
  FILE *infp;
  FILE *outfp;
  int i = 0;
  Genso data[105];
  int youso;

  infp = fopen("genso1.txt", "r");
  if (infp == NULL) {
    printf("Can not open file \n"); exit(1);
  }
  outfp = fopen("genso2.txt", "w");
  if (outfp == NULL) {
    printf("Can not open file \n"); exit(1);
  }

  while (fgets(str, sizeof(str), infp) != NULL) {
    sscanf(str, "%s %d %s", data[i].kigou, &data[i].number, data[i].english);
    i++;
  }
  youso = i;
  fclose(infp);

  quick(data, 0, youso - 1);

  for (i = 0; i < youso; i++)
    fprintf(outfp, "%s %d %s\n" , data[i].kigou, data[i].number, data[i].english);

  fclose (outfp);
  return 0;
}

No.11348
Re:文字でのクイックソート
投稿者---たか(2003/12/20 16:46:02)


ただ気になる点が一つ。quick()で軸をchar *xに持たせていますが、多分
配列の中央または中央より一つ前寄りを選択するので大丈夫だとは思うの
ですが、クイック・ソートのアルゴリズムではこれがソート中に置き換わ
ってしまうとまずいのです。

それを修正した版です。前のプログラムでおかしくなる例があるかどうか
探してみてください。

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

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

typedef struct{
  char kigou[10];
  int number;
  char english[30];
} Genso;

void quick(Genso a[], int left, int right)
{
  int pl = left; 
  int pr = right; 
  char tmp[10];
  
  strcpy(tmp, a[(pl + pr) / 2].kigou); 

  do {
    while (strcmp(a[pl].kigou, tmp) < 0) pl++;
    while (strcmp(a[pr].kigou, tmp) > 0) pr--;
    if (pl <= pr) {
      swap(Genso, a[pl], a[pr]);
      pl++;
      pr--;
    }
  } while (pl <= pr);
  if (left < pr) quick(a, left, pr);
  if (pl < right) quick(a, pl, right);
}

int main(void)
{
  char str[256];
  FILE *infp;
  FILE *outfp;
  int i = 0;
  Genso data[105];
  int youso;

  infp = fopen("genso1.txt", "r");
  if (infp == NULL) {
    printf("Can not open file \n"); exit(1);
  }
  outfp = fopen("genso2.txt", "w");
  if (outfp == NULL) {
    printf("Can not open file \n"); exit(1);
  }

  while (fgets(str, sizeof(str), infp) != NULL) {
    sscanf(str, "%s %d %s", data[i].kigou, &data[i].number, data[i].english);
    i++;
  }
  youso = i;
  fclose(infp);

  quick(data, 0, youso - 1);

  for (i = 0; i < youso; i++)
    fprintf(outfp, "%s %d %s\n" , data[i].kigou, data[i].number, data[i].english);

  fclose (outfp);
  return 0;
}

No.11350
Re:文字でのクイックソート
投稿者---NykR(2003/12/20 16:56:53)


> char *x = a[(pl+pr)/2].kigou;

これだとxの指す文字列の内容が変更される可能性があります。
というか、a[pl].kigouがxと等しく、a[pr].kigouがxより小さくて、
prがplより右にあるときには、確実に変更されます。
配列で宣言してstrcpy等で中身をコピーするようにしましょう。
No.11353
Re:文字でのクイックソート
投稿者---NykR(2003/12/20 17:20:40)


>というか、a[pl].kigouがxと等しく、a[pr].kigouがxより小さくて、
>prがplより右にあるときには、確実に変更されます。

うそじゃ。
まあ偶々全てのキーが違うからこの場合は正しいけど。
No.11355
Re:文字でのクイックソート
投稿者---ｋ王子(2003/12/20 18:28:48)


とても参考になりました！
やはりwhileのところが間違っていたようですね。
ありがとうございました！！