クイックソート

文字のデータ列のクイックソート.

• き,い,お,あ,え,う,か
• か,い,お,あ,え,う,き
• (か,い,お,あ,え,う),き
• (う,い,お,あ,え,か),き
• ((う,い,お,あ,え),か),き
• ((あ,い,お,う,え),か),き
• (((あ,い),(お,う,え)),か),き
• (((あ,い),(う,お,え)),か),き
• (((あ,い),(う,え,お)),か),き
• あ,い,う,え,お,か,き

クイックソートをプログラミングで実装することは多分出来たはずなんですが, どうしても動きが思い出せない.

もう一度プログラミングして見るべきですね.

昔実装したものを見てみました. c++によるマージソートの自前実装 - ncaq

私のクイックソートは他に配列を確保していました.

内部ソートになってないじゃん… ｢クイックソートもどき｣でした.

知識が不足していましたね.

正しくクイックソートを実装しようとしているのですが, なかなかうまくいきません. cgdbでデバッグしてます.

前回と前々回のクイックソートでは適当に最初かその次の領域を選んでたんですが, どうもこの場合停止しないことがあるようですね.

クイックソート - Wikipedia

注：このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。

#include <iostream>

int pivot(int a[], int i, int j) {
    if (i == j) {
        return a[i];
    } else {
        return a[i] < a[i + 1] ? a[i + 1] : a[i];
    }
}

void quick_sort(int a[], int i, int j) {
    /*
       他人のコードのため省略
       アルゴリズムとデータ構造2_06_20171027.pdf
       アルゴリズムとデータ構造2 (6)
       27ページを参照してください
    */
}

int main() {
    // int data[] = {-1, 3, 4, 2, 7, 1, 5, 6};
    int data[] = {-1, 7, 8, 5, 9, 3, 1, 4, 8, 2, 2, 2, 0};
    quick_sort(data, 1, 7);
}

真面目にピボットを選択するか, 適当なピボットが選ばれても停止しないようなアルゴリズムを組まないといけないようですね.

このことで2時間ぐらい悩みました.

そのままではクイックソートのプログラムが実装できないプログラマになってしまうと思って真面目に取り組みました.

[8, 8, 9]のようなデータを渡された時, begin = 0, end = 2, l = 0, r = 1となるので, 単純に

quick_sort(begin, l);
quick_sort(l, end);

とするようなコードだと,

quick_sort(0, 0);
quick_sort(0, 2);

となって無限ループに陥ってしまいます.

無限ループするのを止められません. 適切なピボットの選択方法がわからない. クイックソート実装できると思ってたけど実装できなかった… つらい… どうしてもわからないのでlibc++の実装を見てみようなどとしましたが煩雑すぎて何もわからない.

などと思ってたら, テストコードに終了マークを付けてなかったので, テスト完了と無限ループを区別できてなかったっぽいことが明らかになりました.

あれ, 成功してるじゃん… マジで…? テストコードに成功出力を入れてないせいで成功しても無限ループで失敗だと勘違いしたのでしょうか? は? マジか…

以下が実装したクイックソートです.

クイックソートとしておかしいとか, こういうデータを渡すと無限再帰になるなどの指摘があれば伝えてほしいです.

なんでこんなことに3時間も費やしたんだ私は…

教訓: テストの成功コードはちゃんと書くか, まともなテストフレームワークを使おう.

文字列パターンマッチ

この文字列探索のプログラムのアルゴリズムの話, 去年受けたテキスト処理の講義と内容が被ってますね. テキスト処理の講義内容の詳細は忘却してしまいましたが.

文字列の比較回数とかは私が一番不得意とする類のものですね… 数を数える作業が出来ない… つらい…