qsortを用いた構造体の並べ替え

Question

質問

qsortを使い構造体を並べ直したいのですが、
qsort(S,3,sizeof(Shop),compareWeight);
qsort(&S[i-count],count,sizeof(Shop),compareType);の部分で構造体の値がすべて同じなのでcompareWeight関数、compareType関数の返却値が常に０になり、そのままの順番で構造体を返してほしいのですが、１つずつ前に順番が入れ替わってしまいます。解説お願いします。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
  int price;
  int weight;
  char type[20];
  int date;
  char name[21];
}Shop;

int compareWeight(const void *a,const void *b){
  Shop *A=(Shop *)a;
  Shop *B=(Shop *)b;
  return A->weight-B->weight;
}
int compareType(const void *a,const void *b){
  Shop *A=(Shop *)a;
  Shop *B=(Shop *)b;
  return strcmp(A->type,B->type);
}
int main(void){
  int i,n;
  Shop S[3]={{1,10,"A",1,"a"},
             {1,10,"A",2,"a"},
             {1,10,"A",3,"a"},};
  qsort(S,3,sizeof(Shop),compareWeight);
  for(i=0;i<3;i++){
    printf("%d %d %s %d %s\n",S[i].price,S[i].weight,S[i].type,S[i].date,S[i].name);
  }
  int count=1;
  for(i=1;i<3;i++){
    if(S[i-1].weight==S[i].weight){
      count++;
    }else{
      qsort(&S[i-count],count,sizeof(Shop),compareType);
      count=1;
    }
  }
  if(count!=1){
     qsort(&S[i-count],count,sizeof(Shop),compareType);
  }
  
  for(i=0;i<3;i++){
    printf("%d %d %s %d %s\n",S[i].price,S[i].weight,S[i].type,S[i].date,S[i].name);
  }
  return 0;
}

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

ソートアルゴリズムには様々な種類があり、大きな分類として「安定なソート」と「不安定なソート」に分けられます。 安定なソートというのは大きさが同じ場合に元の順序を維持するソートで、不安定なソートは元の順序を維持することを保証しないソートです。

そして C の標準ライブラリが提供する qsort は不安定なソートです。 なので、質問者の事例では qsort はそういうものですというのが端的な回答です。

簡単な回避方法としては構造体に連番を格納するメンバを用意しておいてソート前に連番をいれておき、値が同じ場合には連番で順序付けをするようにすれば qsort でも安定なソートは可能です。

Comments

[kelt22]

不安定なソートと安定なソートがあるんですね。解説ありがとうございます。