はじめに
まずはともあれ腕試し、この問題を解いてみてくださいな:
【問1】
デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順（昇順）に並び換えたテキストファイル「sorted.txt」を作りなさい。
※各文字列は改行で区切られています。
プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート（整列）アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。
早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ:
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(); } } }
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
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】のようにテーブルには並べられないほど大量のカードの山をソートするには、それに適したアルゴリズムが必要となります。それが今回紹介する「マージ・ソート」です。
