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

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

新規登録して質問してみよう
ただいま回答率
85.50%
ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

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

Q&A

解決済

2回答

5715閲覧

pythonクイックソートの比較回数と交換回数について

WindowppleMacin

総合スコア3

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

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

0グッド

0クリップ

投稿2020/06/25 04:31

編集2020/06/25 05:46

前提・実現したいこと

pythonのクイックソートの関数を定義し、思うように動作できたのですが、比較回数と交換回数をカウントしようとあれこれやっているのですが、うまく動作せず試行錯誤しています。

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

comp は比較回数、sort は交換回数として、実行すると以下のように途中から数字が乱れていきます。

-追記-
比較回数が正しいカウント数にならないです。
どこにインクリメント式を挿入していればいいのでしょうか?
クイックソートにおける比較箇所がいまいちわかりません。

comp = 1 comp = 2 comp = 3 comp = 4 comp = 5 comp = 6 comp = 7 sort = 1 comp = 8 comp = 9 comp = 10 comp = 11 comp = 12 sort = 2 sort = 3 comp = 13 comp = 14 comp = 15 sort = 4 comp = 16 sort = 5 sort = 6 sort = 5 sort = 2

該当のソースコード

カウントする処理を入れる前のクイックソートのソース

python

1def quick_sort(arry): 2 3 n = len(arry) 4 if n <= 1: 5 return arry 6 7 center = arry[0] 8 right=[] 9 left=[] 10 11 for i in range(1,n): 12 if arry[i][2] >= center[2]: 13 left.append(arry[i]) 14 else: 15 right.append(arry[i]) 16 17 r = quick_sort(right) 18 l = quick_sort(left) 19 20 return l+[center]+r

カウント処理を加えてみたソース

python

1def quick_sort(self, data, comp_count, sort_count): 2 3 n = len(data) 4 if n <= 1: 5 return data 6 7 center = data[0] 8 right=[] 9 left=[] 10 11 for i in range(1,n): 12 if data[i][2] >= center[2]: 13 left.append(data[i]) 14 else: 15 right.append(data[i]) 16 comp_count += 1 17 print("comp = %s" %comp_count) 18 19 sort_count += 1 20 print("sort = %s" %sort_count) 21 r = quick_sort(self, right, comp_count, sort_count) 22 sort_count += 1 23 print("sort = %s" %sort_count) 24 l = quick_sort(self, left, comp_count, sort_count) 25 26 self.comp_count = comp_count 27 self.sort_count = sort_count 28 29 return l+[center]+r

試したこと

再帰する際におかしくなっていると推測できたので、カウントの位置を変えたり引数を考えてみたりしましたが、これといった解決法が思いつきません。
カウントする際の変数は、データ構造?を使ってますが特にこだわりはありません。

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

python3.8.2のOS X Mojaveです。

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

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

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

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

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

guest

回答2

0

ベストアンサー

sortが乱れている原因はこちら:

python

1 sort_count += 1 2 print("sort = %s" %sort_count) 3 r = quick_sort(self, right, comp_count, sort_count) 4 sort_count += 1 5 print("sort = %s" %sort_count)

quick_sortの中でsort_countに足していたが、外のsort_countに反映されてません。グローバル変数を使うか、sort_countを戻り値に加えるか、どちらも解決できます。

クイックソートの比較回数はcenterの値によって、ベストケースO(nlogn)からワーストケースO(n^2)まで変動するので、計算する時にご注意ください。

投稿2020/06/25 05:47

YufanLou

総合スコア463

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

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

WindowppleMacin

2020/06/25 06:01 編集

詳細な素早い回答ありがとうございます!!変動するのですか。知らなかったです。比較回数のインクリメントを挿入する位置はあっていますでしょうか?
YufanLou

2020/06/25 06:04

変動するといっても、同じ入力は同じ比較回数です。ただ必ず n*log(n) 回ではありません。比較回数のインクリメント位置は合っていますが、sort_countと同じく、左右分岐の回数を集計していません。
WindowppleMacin

2020/06/25 06:14

左右に分岐した箇所、 if data[i][2] >= center[2]: left.append(data[i]) else: right.append(data[i]) のifとelseの中にもカウントを入れるという事でしょうか?
YufanLou

2020/06/25 06:27

はっきりではなかった、ごめんなさい。そこではありません。左右分岐というのは r = quick_sort(self, right, comp_count, sort_count) l = quick_sort(self, left, comp_count, sort_count) です。 r, comp_count, sort_count = quick_sort(self, right, comp_count, sort_count) l, comp_count, sort_count = quick_sort(self, left, comp_count, sort_count) にして、そして最後に return l+[center]+r, comp_count, sort_count にすれば、グローバル変数を使わなくても大丈夫です。
guest

0

これといった解決法が思いつきません。

グローバル変数に記録してみてはどうでしょうか。

投稿2020/06/25 04:36

maisumakun

総合スコア145121

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

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

WindowppleMacin

2020/06/25 05:09

ありがとうございます! 数字がおかしくなることは無くなりました。 しかし、比較回数が正しいカウント数にならないです。 どこにインクリメント式を挿入していればいいのでしょうか? クイックソートにおける比較箇所がいまいちわかりません。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問