정렬

답변 예

func sort(list: [Int]) -> [Int] {
    var sortedList = list

    for currentIndex in 0..<sortedList.count {
        for sortIndex in (currentIndex + 1)..<sortedList.count {
            if sortedList[currentIndex] < sortedList[sortIndex] {
                let tmp = sortedList[currentIndex]
                sortedList[currentIndex] = sortedList[sortIndex]
                sortedList[sortIndex] = tmp
            }
        }
    }

    return sortedList
}

해설

내림차순 정렬이므로 배열의 0번부터 순서대로 큰 값이 저장되도록 구현합니다.

정렬 아이디어

이 구현은 버블 소트라고 불려, 소트에 있어서 가장 기본이 되는 사고 방식입니다.
[10, 11, 5, 15, 9, 2, 5] 라는 배열을 예를 들어 생각하는 방법을 그림으로 해설합니다.

첫 번째 배열의 이미지는 다음과 같습니다.

우선 0번의 배열에 주목해 갑니다.

시작하기 0번과 1번 값을 비교합니다.
비교한 결과 10 < 11 가 되므로 0번과 1번의 값을 바꿔, 큰 값을 0번에 격납합니다.

다음은 0번과 2번의 값을 비교합니다.11 > 5 이므로 교체는 발생하지 않습니다.

그 후 0번과 3~6번까지의 값을 비교해 가 큰 쪽이면 0번의 값으로 바꿉니다.
그 결과 배열은 다음 상태가 됩니다.

교체가 끝난 결과 0~6번 중 최대값이 0번에 저장되어 있습니다.

다음은 1번의 배열에 주목합니다.

앞의 처리에서 0번이 최대값이라는 것은 확정되어 있기 때문에 1번과 2번부터 비교해 갑니다.10 > 5 그래서 여기는 바꾸지 않습니다.

1번과 3번을 비교합니다.10 < 11 그래서 1번과 3번의 값을 바꿉니다.

여기에서도 역시 마찬가지로 1번과 나머지 4~6번까지 비교해 갑니다.
그 결과 1~6번 중 최대값이 1번으로 저장됩니다.

여기에서 또 주목하는 배열 번호를 2, 3...로 옮겨, 같은 조작을 실시해 가는 것으로 최종적으로 큰 순서로 재정렬할 수 있습니다.

이렇게 큰 것이 거품처럼 위로 올라간다는 의미에서이 정렬 방법은 "버블 정렬"이라고합니다.

구현

나중에 정렬 방식으로 설명한 방법에 따라 구현하면 됩니다.

외부 루프에서 주목하는 요소 번호를 이동하고 배열 수만큼 루프를 돌립니다.currentIndex 가 주목하는 요소 번호가 됩니다.

내부 루프에서 currentIndex에 저장된 값과 비교합니다.sortIndex 가 비교 대상의 요소 번호입니다.
앞서 설명한 대로 비교 대상의 요소 번호는 currentIndex 의 다음으로부터 시작되기 때문에(currentIndex + 1)..<sortedList.count 입니다.
※ 효율이 나빠집니다만 0..<sortedList.count 로서 루프를 돌려도 결과는 바뀌지 않습니다.
if 에서 값을 비교하고 큰 경우 값을 바꿉니다.
교환 처리는 다음과 같이 하고 있습니다.

let tmp = sortedList[currentIndex]
sortedList[currentIndex] = sortedList[sortIndex]
sortedList[sortIndex] = tmp

tmp라는 변수에 sortedList[currentIndex]를 저장합니다.

직관적으로

sortedList[currentIndex] = sortedList[sortIndex]
sortedList[sortIndex] = sortedList[currentIndex]

하고 싶은 곳일지도 모릅니다만, 이렇게 하면 처음의 sortedList[currentIndex] = sortedList[sortIndex] 그리고 sortedList[currentIndex] 의 값이 바뀌어 있습니다.
따라서 sortedList[sortIndex] = sortedList[currentIndex] 에서는 다시 쓴 후의 값을 대입하고 있어 sortedList[currentIndex] 와 sortedList[sortIndex] 는 같은 값이 되어 버립니다.

이를 막기 위해 일시적으로 값을 저장하는 변수로 tmp를 만들고 값을 바꿉니다.

나머지는 루프가 끝까지 돌리면 정렬이 완료됩니다.

정렬이 완료되면 나머지는 반환값으로 sortedList 를 return 해 주면 처리 완료가 됩니다.