多数決がもたらすO(N^3)の悲劇

はじめまして、学生エンジニアの@huyunokiです。

近年うちの研究室のソート界隈では、「スターリンソート」や「ボゴソート」いった崇高なソート手法が席巻しています。確かに彼らは効率的で素晴らしいものかもしれません。しかし、本当にそれで良いのでしょうか？

私はソートアルゴリズムにも民主的な手続きを踏むべきだと考えます。今回はすべての比較判断を多数決で決めるという、極めて公正かつ壮大な無駄を追求したソート、その名も「民主主義ソート」をご紹介します。

「民主主義ソート」とは

バブルソートは隣接する要素 $A$ と $B$ を比較し、 $A > B$ であれば交換します。非常にシンプルで効率的$O(N^2)$ですが、これは独断的な判断です。

民主主義ソートでは、この判断を配列内の残りの全要素に委ねます。

比較準備: 隣接する要素 $A$ と $B$ が、交換すべきか否かを判断します。
投票開始: 配列内の $A$ と $B$ 以外のすべての要素が「有権者」となります。
判定:
- 有権者たちは、「交換すべきか (SWAP)」、「現状維持すべきか (KEEP)」に投票します。
- 多数決で決定された方が、実際の交換ロジックとして採用されます。

【投票ルール】

投票は要素の値の大小とは完全に無関係に行われる必要があります。
なぜなら民主主義だからです。

そこで、最も民主なルールを採用します。

有権者の合計値が：

偶数の場合 $\rightarrow$ SWAP 票（積極的に変更を求める）

奇数の場合 $\rightarrow$ KEEP 票（現状維持を求める）

検証

ご覧の通り、このソートはバブルソートの枠組みで動きます。

外部ループ (パスの回数): $O(N)$
内部ループ (比較の回数): $O(N)$
比較判断 (投票コスト): 1回の比較ごとに、残りの $N-2$ 要素を走査して投票を計算します。これは $O(N)$ のコストです。

よって、民主主義ソートの時間計算量は、

$$O(N) \times O(N) \times O(N) = \mathbf{O(N^3)}$$

となります！従来のバブルソートを遥かに超える非効率性。まさに、「手続きこそがすべてである」という民主主義の側面を見事に体現しています。

Javaで試す

我々はこの崇高なソートを、規律と構造を重んじるJavaで実装し、その哲学を追体験しました。

民主主義ソート

public static void democraticSort(int[] arr) {
        int n = arr.length;
        boolean isSorted = false;
        int passCount = 0;

        // パソコン死なない用(2^30回まで)
        final int MAX_PASSES = 1073741824; 

        // ソートが完了するまでパスを繰り返す
        while (!isSorted) {
            isSorted = true;
            passCount++;

            // パソコン死なない用
            if (passCount > MAX_PASSES) {
                break;
            }
            
            // 外部ループ：配列全体を
            for (int i = 0; i < n - 1; i++) {
                // int current = arr[i]; // 現在の値は投票に影響しないため、不要
                // int next = arr[i + 1]; // 次の値は投票に影響しないため、不要

                // 内部ループ：比較判断のための投票プロセス
                int swapVotes = 0;
                int keepVotes = 0;

                for (int j = 0; j < n; j++) {
                    // 比較対象（arr[i] と arr[i+1]）は投票しない
                    if (j == i || j == i + 1)
                        continue; 

                    // 偶奇による民主主義の投票
                    if (arr[j] % 2 == 0) {
                        swapVotes++;
                    } else {
                        keepVotes++;
                    }
                }

                // 多数決による交換判定
                boolean shouldSwap = swapVotes > keepVotes;

                if (shouldSwap) {
                    // 多数決が交換を決定した場合、実行
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    isSorted = false; // 交換が発生したので、ソートはまだ終わっていない
                }
            }
        }
    }

Java実装の悲劇

Javaという真面目な言語でこのロジックを書くこと自体が風刺的です。特に、このコードでは、たとえ交換が発生しなくても無意味な投票を続ける必要があります。

さらに、投票ルールがランダムにソートを破壊するため、isSorted = true と判定されるためには、奇跡的に全ての比較ポイントで「交換すべきでない」という多数決になるまで、永遠に $O(N^3)$ のプロセスを繰り返す必要があります。

つまり、最悪計算量はボゴソートに匹敵する、あるいはそれを超える「事実上の無限大」となるのです！

まとめ

「民主主義ソート」は、独裁的なソート手法（スターリンソート）へのアンチテーゼとして生まれましたが、その結果はプロセス至上主義がもたらす壮大で無意味な非効率性でした。

ただ、みんなに問います。
非効率性は悪なのかと。しっかり民の意見を聞いてこそ正義なのではないかと。