C#で余分なメモリ領域を使わずに配列内の0と1を並べ替える方法

はじめに

0と1だけで構成された配列を、追加のメモリ領域を使わずに並べ替えたいケースはよくあります。本記事では、「2つのポインタ（low と high）」を使ったインプレース（in-place）手法により、時間計算量 O(N) で効率的にソートする方法を解説します。

アルゴリズムの考え方

まず、low ポインタを配列の先頭に、high ポインタを配列の末尾にそれぞれ配置します。そのうえで、以下のルールに従って処理を進めます。

• array[low] = 0 の場合： 要素はすでに正しい位置にあるため、交換は不要です。low を1つ先に進めます。
• array[low] = 1 の場合： この要素は後方へ移動させる必要があるため、high の位置にある要素と交換し、high を1つ減らします。

low が high を追い越すまでこの操作を繰り返すことで、すべての 0 が配列の前半に、すべての 1 が後半に集まります。

時間計算量：O(N)
空間計算量：O(1)（追加メモリ不要）

C#による実装例

using System;
namespace ConsoleApplication{
    public class Arrays{
        public void SwapZerosOnes(int[] arr){
            int low = 0;
            int high = arr.Length - 1;
            while (low < high){
                if (arr[low] == 1){
                    Swap(arr, low, high);
                    high--;
                }
                else{
                    low++;
                }
            }
        }
        private void Swap(int[] arr, int pos1, int pos2){
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr1 = { 0, 1, 1, 0, 1, 1 };
            a.SwapZerosOnes(arr1);
            for (int i = 0; i < arr1.Length; i++){
                Console.WriteLine(arr1[i]);
            }
        }
    }
}

出力結果

0 0 1 1 1 1

このアルゴリズムのポイント

各要素は最大でも1回しか交換されないため、処理全体は配列の長さに比例した線形時間で完了します。また、元の配列を直接書き換えるため、作業用の配列やバッファが一切不要で、メモリ効率に非常に優れています。この手法は、オランダ国旗問題（Dutch National Flag Problem）の2色版としても知られています。