백준 - 버블 소트 (1517)

let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
var answer = 0

arr = mergeSort(arr)

print(answer)

func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    
    let middle = array.count / 2
    
    let leftArray = mergeSort(Array(array[0..<middle]))
    let rightArray = mergeSort(Array(array[middle..<array.count]))
    
    return merge(leftArray, rightArray)
}

func merge(_ leftArray: [Int], _ rightArray: [Int]) -> [Int] {
    var leftIndex = 0
    var rightIndex = 0
    
    var sortedArray = [Int]()
    
    while leftIndex < leftArray.count && rightIndex < rightArray.count {
        let leftElement = leftArray[leftIndex]
        let rightElement = rightArray[rightIndex]
        
        if leftElement <= rightElement {
            sortedArray.append(leftElement)
            leftIndex += 1
        } else {
            sortedArray.append(rightElement)
            
            let index = leftArray.count + rightIndex
            let sortedIndex = sortedArray.count - 1
            answer += index - sortedIndex
            rightIndex += 1
        }
    }
    while leftIndex < leftArray.count {
        sortedArray.append(leftArray[leftIndex])
        leftIndex += 1
    }
    while rightIndex < rightArray.count {
        sortedArray.append(rightArray[rightIndex])
        rightIndex += 1
    }
    return sortedArray
}

• 버블 정렬의 swap 횟수는 병합 정렬에서 병합 시 원소가 앞으로 이동하는 횟수가 같다.
  • 원소가 앞으로 이동하는 경우는 뒤 그룹의 원소가 먼저 sortedArray 에 저장되는 경우밖에 없다. 따라서 leftElement > rightElement 인 경우에만 이동 횟수를 계산하고 더해주면 된다.
  • 처음에 leftElement < rightElement 라고 코드를 짰는데, 그러면 leftElement == rightElement 인 경우도 이동 횟수를 계산하게 된다. 꼭 = 를 붙여주자