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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

3207閲覧

基本挿入法のフローチャートを正しく書けません 問題点を教えてください

gregolio122

総合スコア14

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2018/08/08 16:49

編集2018/08/08 16:51

前提・実現したいこと

最近C言語の勉強をはじめ、フローチャートの書き方や基本的なアルゴリズムについて学んできました。
C言語で、基本選択法とバブルソートは自力でフローチャート、コードを書くことができたのですが、基本挿入法はうまくいきません。
おそらく、フローチャートに欠陥があるのだと思います。
このサイトを使うのははじめてで、プログラミングともども初心者でいたらない点も多々あるかと思いますが、よろしくお願いいたします。

該当のフローチャート

https://drive.google.com/file/d/1jAaV9yvwbfpJuv65uFaVcpVPvxqTqgfH/view?usp=sharing
フローチャート

ソースコード

#include <stdio.h> int main(void){ int i,j,w; int a[]={4,51,42,23,12}; for(i=0;i<=4;i++){ for(j=i;j>=0;j--){ if(a[i+1]<a[j]&&j>0){ w=a[j]; a[j]=a[i+1]; a[i+1]=w; break; } } } for(i=0;i<=4;i++){ printf("%d ",a[i]); } }

質問

以上のコードを実行すると、出力される配列は4 42 23 23 と一部がソートされた痕跡こそあるものの、正しくソーティングされているとは言えません。
冒頭にも書いた通り、フローチャートに欠陥があると思うのですが、どこに問題がある(あるいは不足している)のでしょうか?

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

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

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

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

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

guest

回答2

0

ベストアンサー

こんにちは。

基本挿入法という言葉は初めて聞きますが、ここに記載されている基本挿入法の事でしたら、アルゴリズム自体の理解が誤っていることは間違いなさそうです。gregolio122さんのプログラムを見ると「交換処理」が入っていますが、基本挿入法にはそのような処理はありません。
基本挿入法は、以下のイメージです。

  1. 全体をソート完了部と未完了部に区分する
  2. 未完了部から1つデータを取ってくる
  3. ソート完了部の挿入位置を見つける
  4. 挿入位置から取ってきたデータの1つ前までのデータを1つ後ろへずらす
  5. 挿入位置へデータをセットする
  6. 2から5を未完了部のデータがなくなるまで繰り返す

ところで、C言語は構造化言語の1つです。そして、フローチャートで構造化言語用のアルゴリズムを記述するには熟練が必要です。C言語になれない内はフローチャートを使わないことをお薦めします。

フローチャートはアセンブラ時代に発明された手法です。goto文時代の記述方式なのです。

投稿2018/08/08 23:55

Chironian

総合スコア23272

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

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

gregolio122

2018/08/09 01:57

ありがとうございます。 「交換処理」をしない、ということが盲点でした。 そもそも、このソートアルゴリズムについて、根本的に考え方を間違えていたのだと思います。 質問する前に、貼っていただいたサイトを参考に勉強していました。 そのサイトで紹介されている「まず前から処理する方法」のことで勘違いをしていたようです。 (前へずらすことを、左にずらす、とします。) 未ソート部分の一番左と、ソート完了部分の右側から左側にかけて比較していって、未ソート部分より大きな数字がソート完了部分にあれば、そこと交換する、という処理を、これまでさせていました。 しかし、交換をするのではなく、未ソート部分を挿入する部分よりも右側のソート完了部分から全てをそれぞれ1つずつ右にずらすのですね。 それは理解できたのですが、それを実現するコードがどうやったら書けるかで今は頭を悩ませています。
gregolio122

2018/08/10 11:35

交換するのではなく、挿入する、ということで、フローチャートとコードを書き直しました。 それで、新しく書いたコードなのですが… #include <stdio.h> int main(void){ int i,j,temp; int a[]={4,51,14,42,8}; // i=未ソート列先頭 j=ソート済列 for(i=1;i<=4;i++){ temp=a[i]; for(j=i-1;j>=0;j--){ if(temp<a[j]&&j>0){ a[j+1]=a[j]; } ・・・① } a[j+1]=temp; } for(i=0;i<=4;i++){ printf("%d ",a[i]); } } このコードを実行しますと、4 51 51 51 (以下略) といった結果になります しかし、①のところに、 }else{ break; }を追加すると、正常にソートができるようになります。 しかし、なぜ、elseとbreak;でうまく動くようになるのかがわかりません…。疑問です…。
Chironian

2018/08/10 11:53

breakしないとjのforループを最後まで回るので、a[j+1]=temp;の時jは-1になっているのでは?
gregolio122

2018/08/11 13:13

ありがとうございます。 仰る通りで、何度か思考実験をしてようやく理解することができました。 バブルソートや最小値選択法は簡単に理解し、自分でコードも書けたので、単純挿入法にここまで苦戦するとは思っていませんでした。 一つ、疑問があるのですが このアルゴリズムは、配列の先頭が最小値になっていなければ使えないのでしょうか? というのも、 #include <stdio.h> int main(void){ int i,j,temp; int a[]={2,6,1,7,5}; // i=未ソート列先頭 j=ソート済列 for(i=1;i<=4;i++){ temp=a[i]; for(j=i-1;j>0;j--){ if(temp<a[j]&&j>0){ a[j+1]=a[j]; }else{ break; } } a[j+1]=temp; } for(i=0;i<=4;i++){ printf("%d ",a[i]); } } というふうに、配列の中身を変えると、先頭が1,2...となるのが正しいのですが 結果が2.1...と先頭が不変となっているようです。 これは、何らかの手段でこのソートアルゴリズムに入る前に配列の先頭を最小値にしておく必要があるということでしょうか?それとも、この単純挿入法のコードにまだ不備がありますでしょうか?
Chironian

2018/08/11 14:17

j>0でループと条件判定しているので、j=0の時と比較しないですね。なので先頭(a[0])は動かないということかと。
episteme

2018/08/11 19:20 編集

> 実現するコードがどうやったら書けるかで今は頭を悩ませています。 tagがC++なんでC++で実装: ```C++ #include <algorithm> // upper_bound, rotate #include <iterator> // next template<typename Iterator> void insertion_sort(Iterator first, Iterator last) { for ( Iterator mid = first; mid != last; ++mid ) { std::rotate(std::upper_bound(first,mid,*mid), mid, std::next(mid)); } } #include <iostream> int main() { int a[] = { 4, 51, 42, 23, 12 }; insertion_sort(a, a+5); for ( int n : a ) std::cout << n << ' '; } ```
gregolio122

2018/08/12 02:04

ありがとうございます。 j>0としていたため、j=0のときにズラす処理が行われないためだったのですね。 納得し、j>=0としたらうまくいきました。 ありがとうございました。 今回は昇順にソートしましたが、降順にソートするときは、一番後ろからだんだん前へと比較していかなければできないのでしょうか?
Chironian

2018/08/12 02:09

経験のため、それはご自身で確認されることをお勧めします。
guest

0

3つほど。コードがうまく行かない場合、閾値・範囲に気をつける必要があります。

1) i
参照範囲を見てみると、for文で0から4まで進めているが、i+1を参照している
2) jの条件
フローチャートとソースで、jの条件が異なる。0の含む・含まない
3) break
フローチャートではbreakが入っていない

投稿2018/08/08 17:57

t_obara

総合スコア5488

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

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

gregolio122

2018/08/09 02:01

breakをフローチャートで表現する方法がわからず(質問前に簡潔に調べはしたのですが)、w→a[i+1]の次にLoop1に向かう矢印を書くことで、Loop2内のbreakを表現していたつもりでした。 誤解を招くような表現で申し訳ないです。
t_obara

2018/08/09 08:43

そうでしたか、breakが入ることでうまく行かないのですが、その点よくご覧になってはいかがでしょうか。 実際に、配列の内容がどのようにソートされていくのかステップを追って確認されると理解しやすいのではないかと思います。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問