Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

マージ・ソート : 巨大データのソート法

C#, VB.NET, C++/CLI で学ぶアルゴリズム

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2008/08/13 14:00

メモリ内に収まらないほどの大きなデータをソートするアルゴリズム「マージ・ソート」。このアルゴリズムを三大.NET言語:C#, VB.NET, C++/CLIで解説します。

目次

はじめに

 まずはともあれ腕試し、この問題を解いてみてくださいな:

【問1】
デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順(昇順)に並び換えたテキストファイル「sorted.txt」を作りなさい。

※各文字列は改行で区切られています。

 プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート(整列)アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。

 早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ:

C#によるバブル・ソート
using System;
using System.IO;
using System.Collections.Generic;

namespace BubbleSort_csharp {

  class BubbleSort {

    // バブル・ソート
    static void Sort<T>(List<T> data) where T : IComparable<T> {
      int lastSwapped = data.Count - 1; // 最後に交換した位置
      do {
        int limit = lastSwapped; // 最終交換位置を上限とする
        lastSwapped = 0;
        for ( int i = 0; i < limit; ++i ) { // 先頭から上限まで
          // 順序の逆転を見つけたら
          if ( data[i].CompareTo(data[i+1]) > 0 ) { 
            T tmp = data[i];     // data[i] と
            data[i] = data[i+1]; // data[i+1] を
            data[i+1] = tmp;     // 交換し
            lastSwapped = i;     // 最終交換位置を更新する
          }
        }
      } while ( lastSwapped != 0 ); // 最終交換位置が0なら完了
    }

    static void Main() {
      // 入力ファイルをオープンし、List<string>に格納する
      TextReader reader = new StreamReader("input.txt");
      List<string> data = new List<string>();
      string line;
      while ( (line = reader.ReadLine()) != null ) {
        data.Add(line);
      }
      reader.Close();
      // ソートして
      Sort(data);
      // 出力ファイルに転写する
      TextWriter writer = new StreamWriter("sorted.txt");
      foreach ( string item in data ) {
        writer.WriteLine(item);
      }
      writer.Close();
    }
  }

}
VB.NETによるバブル・ソート
Imports System.IO

Module BubleSort

  Sub Sort(Of T As IComparable(Of T))(ByVal data As List(Of T))
    Dim lastSwapped As Integer = data.Count - 1 ' 最後に交換した位置
    Do
      Dim limit As Integer = lastSwapped ' 最終交換位置を限度とする
      Dim i As Integer
      lastSwapped = 0
      For i = 0 To limit - 1 ' 先頭から上限まで
        ' 順序の逆転を見つけたら
        If data(i).CompareTo(data(i + 1)) > 0 Then
            Dim tmp As T = data(i) ' data(i) と
            data(i) = data(i + 1) ' data(1+1) を
            data(i + 1) = tmp ' 交換し
            lastSwapped = i ' 最終交換位置を更新
        End If
      Next
    Loop Until lastSwapped = 0 ' 最終交換位置が0なら終了
  End Sub

  Sub Main()
    ' 入力ファイルをオープンし、List(Of String)に格納する
    Dim reader As New StreamReader("input.txt")
    Dim data As New List(Of String)
    Dim line As String
    Do
      line = reader.ReadLine()
      If line = Nothing Then Exit Do
      data.Add(line)
    Loop
    reader.Close()
    ' ソートして
    Sort(data)
    ' 出力ファイルに転写する
    Dim writer As New StreamWriter("sorted.txt")
    For Each item As String In data
        writer.WriteLine(item)
    Next
    writer.Close()
  End Sub

End Module
C++/CLIによるバブル・ソート
using namespace System;
using namespace System::IO;
using namespace System::Collections::Generic;

// バブル・ソート
generic<typename T> where T : IComparable<T>
void Sort(List<T>^ data) {
  int lastSwapped = data->Count - 1; // 最後に交換した位置
  do {
    int limit = lastSwapped; // 最終交換位置を限度とする
    lastSwapped = 0;
    for ( int i = 0; i < limit; ++i ) { // 先頭から上限まで
      // 順序の逆転を見つけたら
      if ( data[i]->CompareTo(data[i+1]) > 0 ) {
        T tmp = data[i];     // data[i] と
        data[i] = data[i+1]; // data[i+1] を
        data[i+1] = tmp;     // 交換し
        lastSwapped = i;     // 最終交換位置を更新
      }
    }
  } while ( lastSwapped != 0 ); // 最終交換位置が0なら完了
}

int main() {
  // 入力ファイルをオープンし、List<String^>に格納する
  StreamReader reader("input.txt");
  List<String^> data;
  String^ line;
  while ( (line = reader.ReadLine()) != nullptr ) {
    data.Add(line);
  }
  reader.Close();
  // ソートして
  Sort(%data);
  // 出力ファイルに転写する
  StreamWriter writer("sorted.txt");
  for each ( String^ item in data ) {
    writer.WriteLine(item);
  }
  writer.Close();
}

 この程度のコードなら技巧の稚拙はあるものの、きちんと勉強していればさほどの苦労はないでしょう。ソート・アルゴリズムの実装を求められていないのならば data.Sort() で済ませてしまえばただのファイル入出力問題になりますね。では第二問:

【問2】
[問1]と同じ。ただし入力ファイルは10GBあります。

 ……さてさて困りました。ソート・アルゴリズムには何の変更を加える必要もないのですが(“バブル・ソートじゃ遅くて使いものにならん!”ってクレームはともかく)、10GBもの文字列をList<string>、すなわちメモリに格納できません。潤沢な資金をつぎ込んでサーバ機を導入し64bit-Vistaでもインストールして湯水のごとくメモリを挿せば、あるいはOracleとかSQLServerとか、データベースのお世話になりますか……。

 バブル・ソートをはじめ、教本で紹介されているソート・アルゴリズムのほとんどはソート対象となるデータがすべてメモリ上にあり、n番目のデータのアクセスが極めて短時間に完了することを前提としています。いわばテーブル上に全カードを並べ、任意のカードどうしを比較/交換できるからこそ、まずまずのスピードでソートできるのです。【問2】のようにテーブルには並べられないほど大量のカードの山をソートするには、それに適したアルゴリズムが必要となります。それが今回紹介する「マージ・ソート」です。


  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • επιστημη(エピステーメー)

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~) だったり わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準講座 (監修) -...

おすすめ記事

All contents copyright © 2006-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5