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

Question

実現したいこと

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

Comments

[episteme]

しつもんはなんですか

[episteme]

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

Answer 1

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

// グローバル変数。s[MAX_LINES] のかわりに。
int comparison_counter;

...
void init_step(){
  comparison_counter = 0;
}

int greater_than(int a, int b) {
  ++comparison_counter;
  return a > b;
}
...


      // while(j >= 1 && a[j - 1] > a[j]){ を修正
      while (j >= 1 && greater_than(a[j - 1], a[j])) {

comparison_counter は s[2] とも s[3] とも異なる値になるはずです。