Table of Contents
  1. Sort
    1. Space & Time Complexity
    2. Sort vs Sorted
    3. Key
    4. Stable sort
    5. Multiple Sort
  2. 마치며

Python의 sort()에 대해서 알아보도록 하겠습니다.

Sort

python 2.3 버전 부터 Merge sort와 Insertion sort를 결합한 Tim sort 알고리즘을 내장 정렬 함수로 사용하고 있습니다. Tim sort에 대한 자세한 사항은 naver D2의 Tim sort에 대해서 알아보자 글을 참고해 주세요.

Space & Time Complexity

python sort 함수는 Tim sort를 이용하고 있으며, 시간 복잡도와 공간 복잡도는 다음과 같습니다.
Best case time complexity O(n)
Average case time complexity O(nlogn)
Worst case time complexity O(nlogn)
Worst case space complexity O(n)

Sort vs Sorted

python은 제자리(in-place)에서 정렬하는 방식과 새로운 정렬된 리스트를 반환하는 두 가지 정렬 방법을 제공합니다.
list.sort() 함수를 이용하면 제자리(in-place) 정렬이 적용되고, sorted() 함수를 이용하면 정렬된 새로운 리스트를 반환합니다.

sorted()를 이용한 제자리 정렬
1
2
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
sorted(a)    # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list.sort()를 이용한 정렬
1
2
3
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
a.sort()     # None
a            # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

두 함수 모두 기본적으로 오름차순으로 정렬하는데, reverse라는 매개변수를 이용하여 역순으로 정렬할 수 있습니다.
참고로 reverse는 key 앞에 정의해야 애러가 나지 않습니다.

reverse option
1
2
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
sorted(a, reverse=True) # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Key

sort()와 list.serted()는 함수를 입력받는 key라는 매개변수를 가지고 있습니다. key는 정렬로 사용할 키를 반환하는 함수로, 이용하면 원하는 정렬을 쉽게 구현할 수 있습니다.

대소문자를 구분하지 않고 정렬
1
2
sorted("This is a test string from Andrew".split(), key=str.lower)
# ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
tuple의 특정 index를 기준으로 정렬
1
2
3
4
5
6
7
student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]
sorted(student_tuples, key=lambda student: student[2]) # sorted by age
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

아래의 예시는 객체의 특정 속성을 이용한 정렬입니다.

객체 특정 속성을 이용한 정렬
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age

    def __repr__(self):
        return repr((self.name, self.grade, self.age))

student_objects = [
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
]

sorted(student_objects, key=lambda student: student.age)
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

참고로 클래스의 인스턴스를 기본적으로 출력하면 아래와 같이 메모리 주소를 반환하게 되어있습니다.

1
2
3
[<__main__.Student at 0x11034a990>,
 <__main__.Student at 0x11034a890>,
 <__main__.Student at 0x11034a790>]

이를 보기 좋게 만들기 위해 Student 클래스에 __repr__ 함수를 override하여 내부 구조를 볼 수 있도록 구현하였습니다.

override __repr__
1
2
3
[('dave', 'B', 10),
 ('jane', 'B', 12),
 ('john', 'A', 15)]

객체의 경우 key를 넣지 않는 경우 기본적으로 __lt__() 함수를 호출하도록 되어있습니다.

__lt__()를 이용한 sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from operator import attrgetter

class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age

    def __repr__(self):
        return repr((self.name, self.grade, self.age))

    def __lt__(self, other):
        return self.age < other.age

student_objects = [
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
]
sorted(student_objects)
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Stable sort

Stable sort 알고리즘이란 정렬 기준이 동일한 값의 순서가 입력된 순서대로 정렬되는 알고리즘을 말합니다. 아래 예제는 색상을 기준으로 정렬하는데, Stable한 경우에는 아래와 같이 각 색상의 숫자 2가 입력된 것과 같이 항상 1 뒤에 있어야 합니다. ('blue', 1)이 항상 ('blue', 2) 앞에 있는 것을 보시면 됩니다.

python의 sort 함수는 stable 합니다.
1
2
3
data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
sorted(data, key=lambda x: x[0])
# [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

다음과 같이 각 색상의 2가 1보다 먼저 나온 경우, stable하지 않은 함수입니다.

1
[('blue', 2), ('blue', 1), ('red', 1), ('red', 2)]

Python은 정렬은 Stable하기 때문에 배열이나 튜플이 중첩된 경우, 먼저 정렬시 첫 번째 원소를 비교하고 해당 원소가 동일한 경우 두 번째 원소를 비교합니다. 따라서 먼저 색상을 오름차순으로 정렬하고, 색상이 같은 경우 숫자를 오름차순으로 정렬하므로 다음과 같은 결과가 나오게 됩니다.

1
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Multiple Sort

다음과 같이 등급과 나이 데이터가 주어졌다고 가정해봅시다.

등급은 A 등급이 B 등급보다 높다고 가정합니다.
1
[('B', 10), ('B', 12), ('A', 11)]

위의 데이터를 등급은 높은 순서대로 정렬하고, 등급이 같은 경우에는 나이가 높은 순으로 정렬해 보도록 하겠습니다. 만약 올바르게 정렬이 된다면 다음과 같은 결과가 나올 것 입니다.

올바른 결과
1
[('A', 11), ('B', 12), ('B', 10)]

위의 목표를 달성하기 위해, 아래와 같은 코드를 만들어 실행해보았습니다.

1
2
3
4
5
6
7
8
student_tuples = [
    ('B', 10), # 등급, 나이
    ('B', 12),
    ('A', 11)
]
student_tuples.sort(key=lambda x: x[0])               # 등급 정렬
student_tuples.sort(reverse=True, key=lambda x: x[1]) # 나이 정렬
student_tuples # [('B', 12), ('A', 11), ('B', 10)]

원하는 결과는 [('A', 11), ('B', 12), ('B', 10)]인데, 최종적으로 나이로만 내림차순 정렬 된 [('B', 12), ('A', 11), ('B', 10)]가 반환됩니다. 이 문제를 해결하기 위해선 정렬 순서를 하위 정렬부터 하도록 변경 해야합니다. 위의 문제에서는 등급 정렬을 한 뒤 동일한 등급에 대해서 나이 정렬을 실행하기 때문에, 나이 정렬이 하위 정렬입니다. 정렬의 순서를 변경하여 실행해 보도록 하겠습니다.

1
2
3
4
5
6
7
8
student_tuples = [
    ('B', 10), # 등급, 나이
    ('B', 12),
    ('A', 11)
]
student_tuples.sort(reverse=True, key=lambda x: x[1])  # 나이 정렬
student_tuples.sort(key=lambda x: x[0])                # 등급 정렬
student_tuples # [('A', 11), ('B', 12), ('B', 10)]

원하는 결과가 나오는 것을 볼 수 있습니다. 그러면 어떠한 이유로 두 정렬의 결과가 다르게 나오는지 과정을 분석해 보겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
# input
[('B', 12), ('B', 10), ('A', 11)]

# 1. 등급 정렬 후 나이 정렬
[('A', 11), ('B', 10), ('B', 12)] # 등급 오름차순 정렬 결과
[('B', 12), ('A', 11), ('B', 10)] # 나이 내림차순 정렬 결과

# 2. 나이 정렬 후 등급 정렬
[('B', 12), ('A', 11), ('B', 10)] # 나이 내림차순 정렬 결과
[('A', 11), ('B', 12), ('B', 10)] # 등급 오름차순 정렬 결과

# 원하는 결과
[('A', 11), ('B', 12), ('B', 10)]

컴퓨터 입장에서는 등급 정렬과 나이 정렬은 컴퓨터 입장에서 서로 독립인 정렬입니다. 따라서 우리는 위에서 말씀드린 Python의 sort는 Stable 하다는 속성을 이용해야합니다. 이를 이용하면 2번 정렬과 같이, 나이를 내림차순으로 정렬한 ('B', 12)를 ('B', 10)를 그대로 유지한 채 등급을 오름차순으로 정렬한 올바른 결과를 얻을 수 있습니다.

마치며

python sort() 함수에 대해 알아보았습니다. 더 자세한 사항은 공식문서를 참고하시기 바랍니다.