クイックソートがセグフォる俺たち

「クイックソート」は配列を順序に従って並べるソートと呼ばれるアルゴリズムの一種です。各ステップで配列をピボットと呼ばれる要素より大きい配列と小さい配列に分割し、それぞれの部分列に対して再帰的に実行することによって配列長nに対して、O(nlogn)という高速な処理を実現しています。

有名なアルゴリズムなので大抵のプログラミング言語にはクイックソートがライブラリとして提供されておりスクラッチから書く必要はないのですが、私はたまに手遊びで書くことがあります。

ただし、このアルゴリズム、「ピボットとの大小関係で分割して再帰的にかければいいんだな」くらいの雑な認識でいるとコーナーケースではまってセグフォったり正しくソートされないことがありますので、自分の備忘のためにいくつか注意点を列挙しておきたいと思います（以下では長さnの整数の配列を昇べきの順でソートすることを考えます）。

1. 先頭と末尾から配列を走査していくとき、スワップのために走査を止めるのはピボット「以下」とピボット「以上」のとき（「未満」と「以上」、「以下」と「超」ではいけない）。

• 配列の先頭の要素がピボットより『大きい』にも関わらず、末尾からの走査でピボットよりも『小さい』要素が見つからないと、配列を二つに分けることができなくなります。例として(5, 4, 3, 6, 3)という配列を考えて、ピボットを'3'としたとき、先頭からの走査は最初の要素'5'で止まります。一方末尾からの走査の際、ピボット「未満」をスワップの基準とすると、末尾からの走査は先頭に至るまで停止せず配列は二つの部分列に分割されません。先頭と末尾を逆にしても同様です。
• ピボット「以下」とピボット「以上」をスワップの基準とすると、ピボットに等しい要素がどちらの部分列に含まれるかが一義的には定まらなくなってしまう点が気になるが、最終的な結果には影響を与えない。

2. スワップした後は走査のインデックスを1進める。

• 一度スワップした要素は二度とスワップする必要はなく、また単純に考えればそのようなことは起き得ないように思える。しかし上記のようにスワップの条件をピボット「以上」「以下」にしてしまうと、ピボットに等しい要素間のスワップが無限に繰り返される可能性があるため、スワップが行われた後は明示的に走査のインデックスを一つ進め、既にスワップが行われた要素を走査の対象から外す必要がある。

3.  再帰呼び出しする際の部分配列の境界に注意。

• 先頭からの走査インデックスをiとしたとき、部分列への分割は0~i, (i+1)~(n-1) とするか、0~(i-1), i~(n-1) とするかわからなくなることがあります。ピボットより小さい、大きいことが保証されているのはどのインデックスまでかを注意する必要があります。

おそらくその他にも気をつけるべきことは多くあるのでしょうが、今日私が気がついたの以上の三点です。今後クイックソートをスクラッチから実装する際には気をつけていきたいと思います。

結論：素直にライブラリ使え。

無事ブラジルの水彩画みたいな暮らし

9/12

25:00ごろに入眠したのだがCPAP のマスクが外れて中途覚醒する。音で起きるというよりは、漏れた空気が顔をなでる感触で目がさめる。朝の目覚めは悪い。総睡眠時間より連続睡眠時間の方が体調に影響しそうだ。16:30 ~ 18:00 のミーティング後の集中力が明らかに落ちていた。コーヒーで無理やり覚醒せずに一旦寝ておいたほうがよかったかもしれない。週の初めから5.5時間も残業してしまった。

9/13

5:00 ~ 6:00 ごろに中途覚醒したような記憶がある。朝の怠さはそれほどでもない。ただ足に力が入らず職場で突然しゃがみこんでしまうことがあった。疲労が蓄積している時に頻発する現象だ。午後はかなり厳しかったのでレッドブルを飲んだ。なんとか持ち直す。17:00 ごろどうにも耐えられなくなって30分ほど眠ってなんとかしのぐ。左胸が握られるように痛む。筋肉痛や神経痛だとは思うが。今日も昼に眠れれば午後これほど辛くなることもなかっただろうが、プレッシャーがあると眠れない。今日も5時間超残業してしまった。これも明日までだ（と良いのだが）。

9/14

6:40 に中途覚醒。そこまで怠さを感じないが昨晩食べ過ぎたので朝食はたまごやきのみ。15:00 ごろろれつが回らなくなり、自分で言っていることがわからなくなってくる。少し眠ると回復して作業できるようになった。しかしこのあたりで判断ミスをして本当は省ける工程に時間を使ってしまい、作業が遅れた。正直この日程でこの体調では仕方がないと思う。ひとまず今日で区切りだ。6時間残業。最寄駅への終電がなくなったのでとなり駅からタクシーで帰った。明日はLから食事に誘われている。楽しみだ。体調を整えていきたい。

以降は9/19 にまとめて書いた。

9/15

10時に今日締め切りの仕事を終えて少し気が抜けていたかもしれない。健康診断の結果が返ってきて、尿酸値が大幅に下がっていた。19:30から新橋でLとビール。疲れていたこともありかなり酔っ払ってしまった。映画や音楽、漫画、仕事や将来の話をこんなに素直に楽しくできたのはいつぶりだろうなあ。

9/16

酔いが残り、午前中はあまり仕事が進まず、23:00退社。ここ二日間はあまり思い切った休憩が取れず、体が強張ったまま仕事をしてしまった。特に脚の冷えが治りきらず、左足だけ冷えが残ってしまうのだ。なんだかこの片方だけ、というのが気持ちが悪く、不安だ。ところで菊地成孔が刺青を入れたらしい。僕も歳をとって体のどこかが悪くなったら、そこにお守り代わりに墨を入れてもらうと良いのではないかとぼんやりと妄想していた。卒中で体の左側に障害が残ったら、左側だけにびっしりと彫り、右側は何もしないというのは結構いい。内臓が悪くなった場合が困りもので、遠からず手術の可能性もあるのだから、ひとまず入れないでおいて、手術痕をデザインに生かした形の刺青を彫ってもらうのがいいだろうか。なんにしろ当分先の話だ。というか先の話であってほしい。

9/17

8時間の睡眠は確保できたが、ここ二週間の疲れと、「休日も進捗を報告するように」というメールのおかげでかなりぐったりしてしまう。布団を干し、靴を洗い、壊れていた無線LANルータを新調するなどした後は、夕方までぐったりと横になっていた。夕食前とその後に二時間ほど仕事をした。ところでこの日タバコが切れた。600円で買って2週間以上持つのだから優秀。ニコチン中毒というわけでもないので当分買わなくていいのだが、やはりタバコを就寝前に一本吸うと生活のリズムができるので、代替物があると助かる。そろそろ電子タバコなどに移行していきたい。そういえばこの日は母が見たいというので超高速参覲交代を見た。「刀と思って抜いたら竹光」のシーンは対比としては2回で十分だけど、3回あるのが肝ですね。

9/18

昨日は0:30 ごろには眠ったはずだが10時近くまで起きられなかった。やはり疲労が蓄積している。昼食後も体がだるくてしかたがない。15:00 ごろからマシになってきたので、まず散髪に行きその後喫茶店で作業。夕食後も2,3時間仕事。明日は絶対に仕事をしたくないので今日中に所定のところまで終わらせる。その後うっかりitunes でデヴィッド・リンチのイレイザーヘッドを買ってしまったので見る。このパッケージ写真がプリントされたシャツをたまに着るので、見ておいたほうがいいかなと思って。わかりやすくグロテスクすぎて、不気味さを減じてしまっているのではないか。2:00 就寝。

イレイザーヘッド　デイヴィッド・リンチ リストア版 (字幕版)

9/19

なんとか9:00ごろに起床。家族から少し遅れて朝食。寒いこと、起きがけに昔付き合っていた子の夢を見てしまったので切なく苦しい気分だった。BS でマイルスデイヴィスの生涯についてのドキュメンタリーをやっていたので見る。自分の弱さを個性に変えること、常に新しいものを求め続けること。クインシー・トループ（マイルス自伝の共著者）がまだ (2011年当時) 存命であったとは知らなかった。あの自伝は上野のワンルームを引き払うときに根津駅の南口を降りてすぐの古本屋に二束三文で売ってしまった。11:00 過ぎに家を出てひたすら電車に乗る。電車は読書や作業に向いている。とにかく気が向いたときに眠れるのがいい。喫茶店や図書館ではそうはいかないのだ。昔行った浅草橋のスペイン料理屋に行きたかったが今日は休業、隣のイタ飯屋に行く。1200円でサラダとパンが食べ放題。なかなか悪くないが、俺はサルシッチャが食いたい気分だった。あとは山手線に乗り集合位相入門の第4章を読んでいた。

集合・位相入門

 とにかく、第4章は一通り押さえよう。他の分野の本を読むときに、位相の知識が足りなくて太刀打ちできないということは、（私が読むもののレベルでは）そうそうないはずなので。

焦燥は疲れの兆候

今週はコンスタントに22:00を超えて残業をした。破綻するかと思ったがなんとか持ちこたえ土日の休日出勤もこなすことができた。「集中力は管理すべき資源である」「睡眠は優先度をつけて処理すべきタスクである」という意識を持つと体調を安定させやすいが、人間の自然の生理をそこまで機械のように管理するのは息苦しいような気もしている。集中力についてだが、6~7時間程度睡眠をとっている場合だと1日で最も高い集中力が維持できるのは3~4時間程度で、その後2~30分休まないとほとんど使い物にならない。休憩が開けると最初の7割程度の集中力になり、そこから2~3時間でまた休憩すると最初の4割くらいだ。

土曜日にいきなり仕事が入ったので納涼船の予定が飛んでしまったのは残念だった。アフターには参加し線香花火などした。Yさんからトートバッグをもらったので大事に使おうと思う。納涼船の中でフリースタイルラップをしようと思ったら単なるだじゃれ大会にしかならなかったというのはこの夏最も微笑ましいエピソードだった。

日曜日は4.5時間ぶっ続けで仕事をして早めに終わらせた。空いた時間で何か楽しいことをしなければ日曜日がもったいないという焦燥感に駆られたが、この焦燥感自体が休憩なく仕事をした疲れのせいだと気がついたので、特に何をするでもなく、帰りに本屋とCD屋に寄るだけで帰った（しかし、16kほど散財してしまった）。

購入物一覧

ルベグ積分入門 (ちくま学芸文庫)

通信の数学的理論 (ちくま学芸文庫)

ネオ(初回限定盤)(DVD付)

SUPER VIEW (初回盤)

Ten(初回盤)

She See Sea