挿入ソートのデータを降順に並べたい　（ランダム、昇順（ソート済み）、降順（ソート済み）の3パターンで）

実現したいこと

挿入ソートを使ってソート済みのデータを降順に並べるプログラムを作成したい。
ランダム、ソート済みデータ（昇順）、ソート済みデータ（降順）の比較回数
使用している言語はC言語です

該当のソースコード

#include <stdlib.h>
#include <time.h>

#define MAX_ELEMENTS    500 
#define OFFSET          100   
#define MAX_LINES       10   
 
int  a[MAX_ELEMENTS] ; 
int  s[MAX_LINES];  
 
int search(int, int);
void init_step(void);
void print_step(int);
void print_header(char *);
int sorted(int);
 
int main(void){
  int i;
  int n; 
 
  srand(time(0));        
 
  print_header("random");
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {
    printf("%4d", n);
    init_step();                  
    for (i = 0; i < n ; i++) {
      a[i] = rand() % n ;     
    }
    search(n, n/3);       

    
    print_step(n);                
  }
 
  print_header("ascending order");
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {
    printf("%4d", n);
    init_step();               
    for (i = 0; i < n ; i++) {
      a[i] = i ;                 
    }
    search(n, n/3);              
    if (!sorted(n)) {             
      fprintf(stderr, "%d not sorted\n", n);
      exit(1);
    }
    print_step(n);               
  }
 

  print_header("descending order");
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {
    printf("%4d", n);
    init_step();                  
    for (i = 0; i < n ; i++) {
      a[i] = n - i ;              
    }
    search(n, n/3);              
    
  
    
    print_step(n);            
  }
 
  return 0;
}
 
void init_step(){
  int i;
  for (i=0; i < MAX_LINES ; i++)
    s[i] = 0;
}
 
void print_step(int n){
  int i;
 
  for (i = 0; i < MAX_LINES ; i++) {
    printf(", %5d", s[i]);
  }
  printf("\n");
 
}
 
void print_header(char *s) {
  int i;
 
  printf("%s\n   n", s);
  for (i = 0; i < MAX_LINES ; i++) {
    printf(", line%d", i);
  }
  printf("\n");
}
 
int sorted(int n) {
  int i;
 
  for (i = 0; i < n - 1; i++) {
    if (a[i] > a[i+1]) return 0;
  }
  return 1;
}
 
int search(int n, int key){
  int i, j, tmp;
 
  s[0]++;      for(i = 1; i < n; i++){
  s[1]++;          j = i;
  s[2]++;          while(j >= 1 && a[j - 1] > a[j]){
  s[3]++;              tmp = a[j];
  s[4]++;              a[j] = a[j - 1];
  s[5]++;              a[j - 1] = tmp;
  s[6]++;              j--;
  s[7]++;          }
  s[8]++;        }
  s[9]++;     return -1;
}```

### 試したこと
教科書やネットの記事などを見ながら昇順の場合は作成できたが、降順のコードがわからない
random
   n, line0, line1, line2, line3, line4, line5, line6, line7, line8, line9
 100,     1,    99,    99,  2683,  2683,  2683,  2683,  2683,    99,     1
 200,     1,   199,   199,  9033,  9033,  9033,  9033,  9033,   199,     1
 300,     1,   299,   299, 21581, 21581, 21581, 21581, 21581,   299,     1
 400,     1,   399,   399, 39501, 39501, 39501, 39501, 39501,   399,     1
 500,     1,   499,   499, 60827, 60827, 60827, 60827, 60827,   499,     1
ascending order
   n, line0, line1, line2, line3, line4, line5, line6, line7, line8, line9
 100,     1,    99,    99,     0,     0,     0,     0,     0,    99,     1
 200,     1,   199,   199,     0,     0,     0,     0,     0,   199,     1
 300,     1,   299,   299,     0,     0,     0,     0,     0,   299,     1
 400,     1,   399,   399,     0,     0,     0,     0,     0,   399,     1
 500,     1,   499,   499,     0,     0,     0,     0,     0,   499,     1
descending order
   n, line0, line1, line2, line3, line4, line5, line6, line7, line8, line9
 100,     1,    99,    99,  4950,  4950,  4950,  4950,  4950,    99,     1
 200,     1,   199,   199, 19900, 19900, 19900, 19900, 19900,   199,     1
 300,     1,   299,   299, 44850, 44850, 44850, 44850, 44850,   299,     1
 400,     1,   399,   399, 79800, 79800, 79800, 79800, 79800,   399,     1
 500,     1,   499,   499, 124750, 124750, 124750, 124750, 124750,   499,     1

episteme

2023/05/22 03:58

しつもんはなんですか

episteme

2023/05/22 04:19

関数:search() がソートしてるんでしょうけど、これ挿入ソートじゃありません。バブルソートです。

回答1件

ベストアンサー

いろいろとツッコミどころがありますが、とりあえず比較回数のカウントをしたかったら以下のようにしてはどうでしょうか。

c
1// グローバル変数。s[MAX_LINES] のかわりに。
2int comparison_counter;
3
4...
5void init_step(){
6  comparison_counter = 0;
7}
8
9int greater_than(int a, int b) {
10  ++comparison_counter;
11  return a > b;
12}
13...
14
15
16      // while(j >= 1 && a[j - 1] > a[j]){ を修正
17      while (j >= 1 && greater_than(a[j - 1], a[j])) {