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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

565閲覧

Pythonの挿入ソートにおけるバグ

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2019/03/21 12:13

前提・実現したいこと

Pythonで挿入ソートを実行しようとしていますが、現在のコードだと誤った出力がされてしまいます。
既に完成している正しいコードをみても、現在書いているコードをどのように修正すればいいかわからず、アドバイスをいただきたいです。

発生している問題・エラーメッセージ

出力結果

入力 A = [1,3,2,8] 出力[8, 1, 8, 8]

求めたい結果

[1,2,3,8]

該当のソースコード

Python

1def solution(A): 2 for i in range(len(A)-1): 3 sort(A, i) 4 print(A) 5 6def sort(A,i): 7 tmp = A[i+1] 8 for j in range(i+1, -1, -1): 9 #自分よりも小さい値が見つかったら 10 if A[j] < tmp: 11 #その要素の1つ後ろに挿入する 12 changeindex = j + 1 13 #挿入するために配列のtmpの1つ前から挿入した挿入したいexchangeindexの要素を1つずつ後ろに移動させる 14 for k in range(i+1, -1, -1): 15 A[k] = A[k-1] 16 A[j] = tmp

補足情報(FW/ツールのバージョンなど)

Python3.6

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

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

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

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

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

_Victorique__

2019/03/21 13:18

入れ替えることでリストのインデックスが変わるのでそこを考慮できていない可能性がありますね。
hayataka2049

2019/03/21 17:08 編集

なんでrange(i+1, -1, -1)で後ろから見ているんでしょうか? しばらく考えてみたけど、やっぱりよくわかりませんでした。 ↑挿入箇所を探すときに後ろから見てるからですかね?
guest

回答1

0

ベストアンサー

1. 修正したコード

なるべく元のコードに沿う形で書き換えました。

python

1# sort(A, i) 関数は無くしました。 2 3def solution(A): 4 # for i in range(len(A)-1): 5 for i in range(len(A)): 6 # tmp = A[i + 1] 7 for j in range(i - 1, -1, -1): 8 tmp = A[i] 9 # if A[j] < tmp: 10 if A[j] > tmp: 11 # for k in range(i + 1, -1, -1): 12 # A[k] = A[k - 1] <- この操作で 8 が大量に生成されていました。 13 A[i] = A[j] 14 A[j] = tmp 15 i = j 16 else: 17 break # <- 挿入ソートにはこの break 文がないといけない。 18 19A = [1,3,2,8] 20solution(A) 21print(A) 22# [1, 2, 3, 8]

2. 改善点

2.1. break 文

挿入ソートには break 文が必要です。break 文がないとバブルソートと、ある意味同じものになってしまいます。それについては以下で書きました。

2.2. reversed 関数

以下の2つは等価です。

python

1range(i - 1, -1, -1) == reversed(range(i))

2.3. 入れ替えの書き方

変数をいれかえるには

python

1# 挿入するために配列のtmpの1つ前から挿入した挿入したい 2# exchangeindexの要素を1つずつ後ろに移動させる 3for k in range(i+1, -1, -1): 4 A[k] = A[k-1] 5A[j] = tmp

2.3.1. 書き方 1

python

1A[i] = A[j] 2A[j] = tmp 3i = j

2.3.2. 書き方 2

Python ではこのように書けます。

python

1A[i], A[j] = A[j], A[i]

投稿2019/03/21 16:10

編集2019/03/21 19:39
nico25

総合スコア830

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

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

hayataka2049

2019/03/21 18:56

2.3. reversed 関数の説明がおかしいままになっています。
nico25

2019/03/21 19:02

早々に修正させていただきました。 ご指摘いただき、誠にありがとうございます。
退会済みユーザー

退会済みユーザー

2019/03/22 00:22

大変わかりやすいご説明をありがとうございました。
nico25

2019/03/22 05:00

恐れ入ります!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問