なぜかマージソート。
メモリを食わずにファイルIOだけでもソートできる優れもののアルゴリズム。時間計算量はΟ(logN)。
データの振り分けと併合を繰り返してソートを行います。
元データ: 1 3|2 5|4 7|6 9|8|0 13|12|11
※ | はその位置で昇順になっていないことを表します。
ファイルを二本用意し、| の位置で出力先を切り替えながら出力します:
ファイル1: 1 3 4 7 8|12
ファイル2: 2 5 6 9|0 13|11
次にこの二本を読み、より小さいほうを取り出して一本の元データに出力します:
元データ: 1 2 3 4 5 6 7 8 9|0 12 13|11
| で区切られた要素列(これを'連'という)はソートされてて、
振り分けと併合によって連の数が減っていきます。
最終的に連の数が1になればソート完了。
C#で書いてみた。ファイルIOはめんどっちーのでBCLコレクションで:
using System;
using System.Collections.Generic;
class Program {
// 二つのキューをマージ(併合)して一つにする
private static void merge<T>(Queue<T> in_q1, Queue<T> in_q2, ICollection<T> out_c) where T : IComparable<T> {
// 入力である二つのキューが共に要素を持っている間
while ( in_q1.Count != 0 && in_q2.Count != 0 ) {
// より小さい要素を取り出して出力する
out_c.Add(( in_q1.Peek().CompareTo(in_q2.Peek()) < 0 )? in_q1.Dequeue():in_q2.Dequeue());
}
// キューに残る(取り出されなかった)要素を出力する
while ( in_q1.Count != 0 ) { out_c.Add(in_q1.Dequeue()); }
while ( in_q2.Count != 0 ) { out_c.Add(in_q2.Dequeue()); }
}
// 一つの入力列を二つのキューに分割する
private static bool split<T>(ICollection<T> in_c, Queue<T> out_c1, Queue<T> out_c2) where T : IComparable<T> {
T last = default(T);
Queue<T> out_c = out_c1;
bool switched = false;
foreach ( T current in in_c ) {
// 直前の要素より小さな要素を読み込んだら出力キューを切り替える
if ( last != null && current.CompareTo(last) < 0 ) {
out_c = (out_c == out_c1) ? out_c2 : out_c1;
}
out_c.Enqueue(last = current);
// 一度でも切り替えが起こったらswitchedをtrueにする
if ( !switched ) switched = (out_c == out_c2);
}
return switched;
}
public static void print<T>(string head, IEnumerable<T> collection) {
Console.Write("{0} : ", head);
foreach ( T item in collection ) {
Console.Write("{0} ", item);
}
Console.WriteLine();
}
public static void merge_sort<T>(ICollection<T> data) where T : IComparable<T> {
Queue<T> q1 = new Queue<T>();
Queue<T> q2 = new Queue<T>();
while ( split(data, q1, q2) ) {
Console.WriteLine("--------------------------------");
print("input ", data);
Console.WriteLine("split:");
print("queue1 ", q1);
print("queue2 ", q2);
data.Clear();
merge(q1, q2, data);
Console.WriteLine("merge:");
print("output ", data);
q1.Clear();
q2.Clear();
}
}
public static void Main() {
List<int> data = new List<int>(new int[] { 1, 3, 2, 5, 4, 7, 6, 9, 8, 0, 13, 12, 11 });
merge_sort(data);
Console.WriteLine("--------------------------------");
print("result ", data);
}
}
...のんちゃんがVBがんがってるらしいから、
僕もグチこぼしてばっかじゃなくVBでも書いてみる:
Imports System
Imports System.Collections.Generic
Module Program
' 二つのキューをマージ(併合)して一つにする
Private Sub merge(Of T As IComparable(Of T))(ByVal in_q1 As Queue(Of T), ByVal in_q2 As Queue(Of T), ByVal out_c As ICollection(Of T))
' 入力である二つのキューが共に要素を持っている間
While in_q1.Count <> 0 AndAlso in_q2.Count <> 0
' より小さい要素を取り出して出力する
If in_q1.Peek().CompareTo(in_q2.Peek()) < 0 Then
out_c.Add(in_q1.Dequeue())
Else
out_c.Add(in_q2.Dequeue())
End If
End While
' キューに残る(取り出されなかった)要素を出力する
While in_q1.Count <> 0
out_c.Add(in_q1.Dequeue())
End While
While in_q2.Count <> 0
out_c.Add(in_q2.Dequeue())
End While
End Sub
' 一つの入力列を二つのキューに分割する
Private Function split(Of T As IComparable(Of T))(ByVal in_c As ICollection(Of T), ByVal out_q1 As Queue(Of T), ByVal out_q2 As Queue(Of T)) As Boolean
Dim last As T = Nothing
Dim out_q As Queue(Of T) = out_q1
Dim switched As Boolean = False
For Each current As T In in_c
' 直前の要素より小さな要素を読み込んだら出力キューを切り替える
If last IsNot Nothing AndAlso current.CompareTo(last) < 0 Then
If out_q Is out_q1 Then
out_q = out_q2
' 一度でも切り替えが起こったらswitchedをtrueにする
switched = True
Else
out_q = out_q1
End If
End If
last = current
out_q.Enqueue(current)
Next
Return switched
End Function
Public Sub print(Of T)(ByVal head As String, ByVal collection As IEnumerable(Of T))
Console.Write("{0} : ", head)
For Each item As T In collection
Console.Write("{0} ", item)
Next
Console.WriteLine()
End Sub
Public Sub merge_sort(Of T As IComparable(Of T))(ByVal data As ICollection(Of T))
Dim q1 As New Queue(Of T)
Dim q2 As New Queue(Of T)
While split(data, q1, q2)
Console.WriteLine("-------------------------")
print("input ", data)
Console.WriteLine("split:")
print("queue1 ", q1)
print("queue2 ", q2)
data.Clear()
merge(q1, q2, data)
Console.WriteLine("merge:")
print("output ", data)
q1.Clear()
q2.Clear()
End While
End Sub
Sub Main()
Dim data As New List(Of Integer)(New Integer() {1, 3, 2, 5, 4, 7, 6, 9, 8, 0, 13, 12, 11})
merge_sort(data)
Console.WriteLine("-------------------------")
print("result ", data)
End Sub
End Module