再帰型マージソート

sort_test.swift

import Foundation

class Person : Comparable{
    let id : Int
    let name : String

    init( id : Int, name : String ) {
        self.id = id;
        self.name = name;
    }

    init() {
        self.id = 0
        self.name = ""
    }

    func get_id() -> Int { return id }
    func get_name() -> String { return name }

};

func < ( left: Person, right: Person ) -> Bool {
    return left.get_name() < right.get_name()
}

func == ( left: Person, right: Person ) -> Bool {
    return left.get_name() == right.get_name()
}

class Sort<T:Comparable> {
    var buf : Array<T>
    var array : Array<T>

    init() {
        buf = [T]()
        array = [T]()
    }

    // ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
    func merge( index_b: Int, index_c: Int, index_e: Int ) {
        // 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
        if index_b + 1 == index_e {
            if array[index_e] < array[index_b] {
                let tmp = array[index_e]
                array[index_e] = array[index_b]
                array[index_b] = tmp
            }
            return
        }

        // index_1とindex_2を動かしながら，小さい方を順次index_bufへ書き込む
        var index_1 = index_b
        var index_2 = index_c + 1
        var index_buf = index_b

        while true {
            if array[index_1] < array[index_2] {
                buf[index_buf] = array[index_1]
                index_buf += 1

                // index_1が最後まで到達したらindex_2側を順番に見て終了
                if index_1 == index_c {
                    while index_2 <= index_e {
                        buf[index_buf] = array[index_2]
                        index_buf += 1
                        index_2 += 1
                    }
                    break
                }
                index_1 += 1
            } else {
                buf[index_buf] = array[index_2]
                index_buf += 1

                // index_2が最後まで到達したらindex_1側を順番に見て終了
                if index_2 == index_e {
                    while index_1 <= index_c {
                        buf[index_buf] = array[index_1]
                        index_buf += 1
                        index_1 += 1
                    }
                    break
                }
                index_2 += 1
            }
        }

        // バッファから元配列へコピー
        for i in index_b ... index_e {
            array[i] = buf[i]
        }

        return
    }

    // 再帰的に呼び出す関数
    func merge_sort( index_b: Int, index_e: Int ) {
        let index_c = ( index_b + index_e ) / 2

        // 左側をソート
        if index_b != index_c {
            merge_sort( index_b:index_b, index_e:index_c )
        }

        // 右側をソート
        if (index_c + 1) != index_e {
            merge_sort( index_b:index_c + 1, index_e:index_e )
        }

        // 左と右をマージ
        merge( index_b:index_b, index_c:index_c, index_e:index_e )

        return
    }

    // mainから呼ぶソート関数
    func merge_sort( vec : inout [T] ) {
        // ソート対象の配列をメンバ変数にコピー
        array = vec

        // マージ中のソート結果を一時的に記憶するバッファ
        buf = vec

        // マージソート
        merge_sort( index_b:0, index_e:vec.count - 1 )

        // ソート済み配列をvecにコピー
        vec = array
    }

}

// 時間測定のための変数
var tp_start = timespec()
var tp_end = timespec()

/******** 標準入力からデータを読み込み ********/
var array_people = Array<Person>()
var id : Int
var name : String

clock_gettime(CLOCK_REALTIME, &tp_start)

extension String: Collection {}
while let input : String = readLine() {
    let values = input.split( separator: " " )
    array_people.append( Person( id: Int(values[0])!, name: values[1] ) )
}

clock_gettime(CLOCK_REALTIME, &tp_end)
print( "reading : \(Double(tp_end.tv_sec - tp_start.tv_sec) + Double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0)" )

/******** 読み込んだデータをソート ********/
var sort = Sort<Person>()

clock_gettime(CLOCK_REALTIME, &tp_start)

sort.merge_sort( vec : &array_people )

clock_gettime(CLOCK_REALTIME, &tp_end)
print( "sorting : \(Double(tp_end.tv_sec - tp_start.tv_sec) + Double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0)" )

// ソート済み確認
for i in 1 ..< array_people.count {
    if array_people[i] < array_people[i-1] {
        print( "ERROR" )
    }
}