Skip to content

Instantly share code, notes, and snippets.

@albow-net albow-net/sort_test.swift
Last active Aug 22, 2017

Embed
What would you like to do?
再帰型マージソート
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" )
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.