Swift ) 정렬 (1)

 

안녕하세요 :) Zedd입니다.

간단한 정렬부터 복잡한 정렬까지 차근차근 공부해보려고 합니다.

 

이 글에서는 간단한 정렬을 먼저 해볼게요.

숫자 배열이 있고 그걸 오름차순으로 정렬하고 싶습니다. 

var numbers = [50, 1, 200, 40, 39]

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

sortedNumber.forEach {
    print($0)
}
//1
//39
//40
//50
//200

이렇게 할 수 있겠죠! (오늘 예제코드에서는 closure내부에서 생략을 최대한 안하려고 합니다.)

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

이 코드가 어떻게 동작하는지 알아봅시다.

먼저 sorted 문서부터 봅시다.

 

# sorted

areInIncreasingOrder파라미터가 있는데, 

첫번째 인수가 두번째 인수보다 먼저 정렬되어야 하는 경우 true를 리턴하는겁니다.

그렇지 않으면 false를 리턴하면됩니다.

그럼 같이 해보겠습니다.

 

# 첫번째 비교

이렇게 배열이 있습니다. 

sorted가 시작되고,

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

number1에는 1이, number2에는 50이 할당됩니다.

 

Q : number1이 50이고. number2가 1아니야?

A : 아닙니다! Combine ) Operator (4) 에서 본것처럼 Max같은 경우에는 number1이 50이고 number2가 1이겠지만 sorted는 아니더라구요. number1이 index+1, number2가 index라고 생각하시면 될듯. 

그럼 결과적으로

number1 == 1
number2 == 50
number 1 < number2 == 1 < 50

을 검사하게 됩니다. 1이 50보다 작은건 true이죠! 

첫번째 인수가 두번째 인수보다 먼저 정렬되어야 하는 경우 true리턴.

여기서 첫번째 인수는 1이고 두번째 인수는 50입니다.

true를 리턴했으므로 

1,  50 순서로 정렬되게 됩니다.

 

"첫번째 인수가 두번째 인수보다 먼저 정렬되어야 하는 경우 true리턴"을 그냥 순서를 바꾼다고 표현할게요. 

 

# 두번째 비교

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

number1 == 200
number2 == 50
number 1 < number 2 == 200 < 50

200은 50보다 작지 않으므로 false가 리턴되게 되며, 이 경우 순서가 바뀌지 않고 그대로 있습니다.

 

# 세번째 비교.

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

number1 == 40
number2 == 200
number 1 < number 2 == 40 < 200

true이므로 순서가 바뀌게 됩니다.

1, 50, 40, 200순이 되죠.

 

# 네번째 비교

이렇게 될 것 같지만 아닙니다. 

방금 40과 200을 바꿨잖아요? 그래서 1, 50, 40, 200순이 되었지만, 40앞에 50이 있는 상황입니다.

40이 내가 진짜 여기에 있는 위치인가 보장하기 위해 앞에 값과 다시 한번 비교하게 됩니다.

(만약 1, 10, 50, 200순이었다 하더라도 한번 더 검사하게 됩니다. 검사해서 보장해야하기 때문)

 

다시 이렇게 와서

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

비교를 합니다.

number1 == 40
number2 == 50
number1 < number2 == 40 < 50

true죠. 순서를 바꾸게 됩니다. 

 

# 다섯번째 비교

역시 40이 내가 진짜 내 앞에 값보다 클까?라는 것을 확인해야합니다.

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

number1 == 40
number2 == 1

number1 < number2 == 40 < 1

40이 1보다 작지는 않죠. false를 리턴하게 되고 40은 이 위치에 있는것으로 결정이 납니다.

 

# 여섯번째 비교

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

그럼 다시 여기로 가서 시작합니다.

number1 == 39
number2 == 200
number1 < number2 == 39 < 200

true를 리턴합니다.

순서가 바뀌게 되고 

1, 40, 50, 39, 200이 됩니다.

 

# 일곱번째 비교

하지만 1, 40, 50, 39, 200는 올바른 순서가 아닙니다.

다시 50으로 가서 

let sortedNumber = numbers.sorted { (number1, number2) -> Bool in
    return number1 < number2
}

number1 == 39
number2 == 50
number1 < number2 == 39 < 50

true이므로 자리를 바꿉니다.

# 여덟번째 비교

역시나 39앞에 39보다 작은 숫자가 있는건지 없는건지 확인하기 위해 40과 한번더 비교를 진행합니다. 

number1 == 39
number2 == 40
number1 < number2 == 39 < 40

true이므로 자리를 바꿉니다.

 

# 아홉번째 비교

역시나 1과 비교를 해야하므로

number1 == 39
number2 == 1
number1 < number2 == 39 < 1

false이므로 자리를 바꾸지않고 그대로 있습니다.

이렇게 정렬이 끝나게 됩니다!

 

Complexity는 n이 시퀀스의 길이일 때 O(nlogn)이 나오게 됩니다. 

 

오늘은 간단하게 정렬이 어떻게 이루어지는지만 봤고, 다음글에서는 조금 더 복잡한 정렬을 해보겠습니다. 

정렬 (2) 읽으러 가기