Swift 병합 정렬
병합 정렬 자료 구조
- N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.(병합 정렬)
- 첫째 줄에 수의 개수
N(1 <= N <= 1,000,000)이 주어진다. - 둘째 줄부터 N개의 줄에는 숫자가 주어진다.
- 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다.
- 수는 중복되지 않는다.
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
import Foundation
var list = [Int]()
var number = 0
func makeList()
{
if let inputNumber = readLine()
{
if var intNumber = Int(inputNumber)
{
if intNumber >= 1 && intNumber <= 1000000
{
number = intNumber
while intNumber > 0
{
if let inputElement = readLine()
{
if let intElement = Int(inputElement)
{
list.append(intElement)
}
}
intNumber = intNumber - 1
}
}
}
else
{
print("no input")
}
}
}
func mergeSort(array: [Int], left: Int, right: Int)
{
var mid: Int;
if left < right
{
mid = (left + right) / 2
mergeSort(array: list, left: left, right: mid)
mergeSort(array: list, left: mid+1, right: right)
merge(array: list, left: left, mid: mid, right: right)
}
}
func merge(array: [Int], left: Int, mid: Int, right: Int)
{
var a: Int, b: Int, c: Int
a = left
b = mid + 1
c = left
var tempList = Array(repeating: 0, count: number)
while a <= mid && b <= right
{
if array[a] < array[b]
{
tempList[c] = array[a]
a = a + 1
} else
{
tempList[c] = array[b]
b = b + 1
}
c = c + 1
}
if a > mid
{
for element in b...right
{
tempList[c] = array[element]
c = c + 1
}
} else
{
for element in a...mid
{
tempList[c] = array[element]
c = c + 1
}
}
for element in left...right
{
list[element] = tempList[element]
}
}
func printList()
{
for element in 0..<number
{
print(list[element])
}
}
makeList()
mergeSort(array: list, left: 0, right: number - 1)
printList()