実現したいこと
挿入ソートを使ってソート済みのデータを降順に並べるプログラムを作成したい。
ランダム、ソート済みデータ(昇順)、ソート済みデータ(降順)の比較回数
使用している言語は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
回答1件
あなたの回答
tips
プレビュー