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

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

ただいまの
回答率

87.92%

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,416

前提・実現したいこと

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

該当のソースコード

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

def quick_sort(arry):

    n = len(arry)
    if n <= 1:
        return arry

    center = arry[0]
    right=[]
    left=[]

    for i in range(1,n):
        if arry[i][2] >= center[2]:
            left.append(arry[i])
        else:
            right.append(arry[i])

    r = quick_sort(right)
    l = quick_sort(left)

    return l+[center]+r


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

def quick_sort(self, data, comp_count, sort_count):

    n = len(data)
    if n <= 1:
        return data

    center = data[0]
    right=[]
    left=[]

    for i in range(1,n):
        if data[i][2] >= center[2]:
            left.append(data[i])
        else:
            right.append(data[i])
        comp_count += 1
        print("comp = %s" %comp_count)

    sort_count += 1
    print("sort = %s" %sort_count)
    r = quick_sort(self, right, comp_count, sort_count)
    sort_count += 1
    print("sort = %s" %sort_count)
    l = quick_sort(self, left, comp_count, sort_count)

    self.comp_count = comp_count
    self.sort_count = sort_count

    return l+[center]+r

試したこと

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

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

python3.8.2のOS X Mojaveです。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/06/25 14:50 編集

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

    キャンセル

  • 2020/06/25 15:04

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

    キャンセル

  • 2020/06/25 15:14

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

    キャンセル

  • 2020/06/25 15: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
    にすれば、グローバル変数を使わなくても大丈夫です。

    キャンセル

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/06/25 14:09

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

    キャンセル

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

  • ただいまの回答率 87.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る