質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%

Q&A

解決済

1回答

577閲覧

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

marimo77

総合スコア3

0グッド

0クリップ

投稿2023/05/22 03:34

実現したいこと

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2023/05/22 03:58

しつもんはなんですか
episteme

2023/05/22 04:19

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

回答1

0

ベストアンサー

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

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])) {

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

投稿2023/05/22 05:04

int32_t

総合スコア20832

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問