python의 sorted 함수는 데이터를 특정한 기준으로 정렬해주는 함수입니다. tim sort를 쓰기 때문에 시간 복잡도는 O(nlogn)임이 알려져 있습니다. 특정한 기준은 key 함수로 설정해 줄 수 있어요.
먼저 어떤 인자들이 있는지 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor3.png)
3개의 인자가 있는데요. __iterable, key, reverse 이렇게 3개가 있습니다.
- __iterable
- 순회 가능한 객체
- 보통 list를 많이 사용하는 편입니다.
- key
- sort order를 정하기 위한 key 함수
- reverse
- 정렬 결과를 뒤집는다면 True, 아니면 False
대략 이렇습니다. 예제를 몇 개 보면서 이해해 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor1.png)
예제 1번 프로그램을 봅시다. li에 1, -2, 3, 4, 5가 있습니다. list는 순회 가능하기 때문에 1번째 인자로 li를 넣었습니다. sorted는 정렬된 결과를 돌려줍니다. 따라서, 2번째 줄에 sorted(li)의 결과를 받습니다. 이 결과를 3번째 줄에서 출력하고 있어요.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor2.png)
결과는 -2, 1, 3, 4, 5가 나옵니다. 오름차순으로 정렬되었음을 볼 수 있어요.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor4.png)
이제 예제 2번을 보겠습니다. 아까와 다른 것은 reverse를 True로 준 것입니다. 이 경우, 오름차순의 결과를 뒤집습니다. -2, 1, 3, 4, 5를 뒤집은 결과는 5, 4, 3, 1, -2 순서대로 나오는 것입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor5.png)
따라서, reverse 인자를 True로 주면 오름차순이 아닌 내림차순으로 정렬해서 보여줍니다.
이제 key 함수를 볼게요. key 함수는 sort order를 정하기 위해서 쓴다고 했어요. sorted 함수에서 key 여러 개를 정렬 기준으로 잡기 위해, key 함수를 쓸 수 있습니다. 그리고 이것과 잘 맞는 것은 tuple입니다. 튜플이 1번째 원소 오름차순으로 정렬합니다. 1번째 원소가 같으면 2번째 원소 오름차순, 2번째 원소가 같으면 3번째 원소 오름차순으로 정렬한다는 것을 역이용 합니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor6-1.png)
보시면, lambda k: (k[0], -k[1])가 있는데요. 이것이 key 함수입니다. 이게 무엇을 의미하는가? li를 보시면 (1, 2), (1, -2) 등으로 선언되었음을 볼 수 있는데요. tuple입니다. 이것이 어떻게 해석이 될까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor10.png)
iterable한 객체에 들어있는 item 하나 하나를 키라고 해요. (1, -2)는 위 그림과 같이 표현될 겁니다. key 함수는 key k가 (k[0], -k[1])로 맵핑이 된다고 하는군요? lambda k: (k[0], -k[1])의 의미는 아래 그림과 같아요.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor11.png)
key 함수에 의해, 아이템 (1, -2)는 (1, 2)로 바뀌었습니다. 즉, sort order를 할 때 (1, -2)는 (1, -2)를 가지고 하는 것이 아닙니다. key 함수에 의해 변환된 (1, 2)를 가지고 하는 것입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor12.png)
이제 (1, 2)를 예제 3번의 key 함수로 변환해 봅시다. 그러면, (1, -2)가 나옵니다. 즉, (1, 2)는 sort order를 할 때 (1, 2)를 가지고 하는 게 아니라, (1, -2)를 가지고 합니다. tuple은 1번째 원소 오름차순, 1번째 원소가 같으면 2번째 원소 오름차순입니다. 이렇게 order 가 들어갑니다.
따라서, 예제 3의 sorted는 (1, -2)보다 (1, 2)가 오더가 앞서게 됩니다. 최종적으로는 1번째 원소 오름차순, 1번째 원소가 같으면 2번째 원소 내림차순으로 정렬된 결과가 나옵니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor7.png)
예제 3의 결과는 위와 같습니다. 즉, 여러 정렬 기준을 적용할 경우에는 key 함수를 이용하고, 그 안에서 tuple을 쓴다는 것이 핵심입니다.
그런데 key 함수를 적용하기 까다로울 때가 있습니다. 예를 들어, 1번째 요소 오름차순으로 정렬해야 합니다. 1번째 요소가 같다면 2번째 요소 내림차순으로 정렬해야 하는데요. 2번째 요소가 문자열이였다 합시다. 이런 경우에 어떻게 해야 할까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor8-1.png)
sorted를 2번 쓰면 됩니다. 어떻게 했나요?
- 2번째 요소를 기준으로 내림차순으로 정렬했습니다.
- 그 결과를 가지고 1번째 요소를 기준으로 오름차순 정렬했습니다.
이러면 끝날까요? 놀랍게도 요구 사항을 만족 시킵니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor13.png)
먼저 1번째 요소 기준으로 내림차순 정렬할 겁니다. 그러면, 노란색을 기준으로 정렬이 될 겁니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor14-1.png)
다음에 1번쨰 요소 기준으로 오름차순 정렬이 된다고 했으니, 군청색 기준으로 정렬이 됩니다. 그런데 여기서 중요한 것은 python의 sort는 stable sort라는 것입니다. order가 같을 때, 기존의 순서가 바뀌지 않는다는 말입니다. 즉, (1, ‘ba’)와 (1, ‘a’)는 order가 같기 때문에, (1, ‘ba’)가 (1, ‘a’)보다 먼저 옵니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor15.png)
따라서, 위와 같은 결과가 나오게 됩니다. 실행 결과를 볼까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/py_sor9.png)
제가 설명했던 것과 똑같이 나왔음을 볼 수 있어요. stable sort의 특성을 이용해서, 우선 순위 역순으로 정렬을 차근차근 하는 방법도 있습니다. 이제 문제를 하나 드리겠습니다. 예제 3번을 예제 4번과 같은 방법으로 정렬해 보세요.