정렬 - list.sort(), sorted()

본 문서는 python 공식 문서의 정렬 HOW TO 문서를 학습하고 정리한 것입니다.

 

파이썬 리스트에는 리스트를 제자리에서 (in-place) 수정하는 내장 list.sort() 메서드가 있다.

또한, 이터러블로부터 새로운 정렬된 리스트를 만드는 sorted() 내장 함수가 있다.

정렬 기초

sort() 메서드와 sorted() 내장 함수가 한창 헷갈릴 때 내가 했던 많은 실수들은

a = [5, 1, 2, 3]
a = a.sort()

ㅠㅠ

언뜻 문제가 없는 것 같아보이지만

list.sort() 메서드는 list를 정렬하여 저장한 뒤 return None하는 함수이기 때문에

이렇게 한 뒤 a를 출력해보면 None이 출력된다.

때문에 다음과 같이 사용해야 한다.

 

a.sort()
print(a)

 

혹은 sorted() 함수를 사용하여

 

sorted(a)

 

내가 헷갈렸던 이유는 sorted(a)는 a를 실질적으로 변환시키지 않은 채(inplace = False) sorting된 a 리스트를 반환하기 때문에 정렬된 결과값을 따로 저장해주어야 했는데 sort() 메서드는 inplace = True이기 때문에 이 둘이 헷갈려서 이렇게 되고 만 것... 열 번쯤 실수한 끝에 헷갈리지 않게 되었다.

 

한편 list.sort() 메서드는 리스트에게만 정의되지만, 이와 달리 sorted() 함수는 모든 이터러블을 받아들인다.

즉 다음과 같은 사용도 가능하다.

 

sorted({1:'D', 2:'B', 4:'C', 3:'A'})

 

이 경우 {1:'D', 2:'B', 4:'C', 3:'A'}의 key가 정렬된 형태의 [1,2,3,4]가 반환된다.

키 함수

list.sort()와 sorted()는 모두 비교하기 전에 각 리스트 요소에 대해 호출할 함수를 지정하는 key 매개변수를 가지고 있다.

 

sorted("This is a test string from eunha".split(), key=str.lower)
# ['a', 'eunha', 'from', 'is', 'string', 'test', 'This']

 

split된 모든 단어들을 lower()시킴으로써 대소문자를 구분하지 않는 문자열 비교가 가능해졌다.

 

key 매개변수의 값은 단일 인자를 취하고 정렬 목적으로 사용할 키를 반환하는 함수여야 한다.

키 함수가 각 입력 레코드에 대해 정확히 한 번 호출되기 때문에 빠르다!

 

일반적인 패턴(그리고 내가 지금까지 많이 사용해왔던 패턴)은 객체의 인덱스 중 일부를 키로 사용하여 복잡한 객체를 정렬하는 것이다.

 

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

 

student_tuples라는 리스트에 들어있는 튜플들에 대하여 각 튜플의 세번째 요소 (index는 2)를 기준으로 정렬하였다.

 

이름있는 어트리뷰트를 가지는 객체에 대해서도 작동한다.

 

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('dave', 'B', 10), Student('john', 'A', 15), Student('jane', 'B', 12)]
sorted(student_objects, key = lambda student: student.age)
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

 

키 함수는 정렬되는 객체에 직접 의존할 필요가 없다. 키 함수는 외부 자원에 액세스할 수도 있다.

예를 들어, 학생 성적이 딕셔너리에 저장되어 있다면, 학생 이름의 별도 리스트를 정렬하는 데 사용할 수도 있다.

 

students = ['dave', 'john', 'jane']
newgrades = {'john':'F', 'jane':'A', 'dave':'C'}
sorted(students, key = newgrades.__getitem__)
# ['jane', 'dave', 'john']

 

lambda를 써서도 가능하다. (내 기준 조금 더 직관적이고, 좀 더 느리다.)

 

students = ['dave', 'john', 'jane']
newgrades = {'john':'F', 'jane':'A', 'dave':'C'}
sorted(students, key = lambda x:newgrades[x])
# ['jane', 'dave', 'john']

 

operator 모듈 함수

위에서 보여준 키 함수 패턴은 매우 일반적이다.

그 외에 파이썬은 액세스 함수를 더 쉽고 빠르게 만드는 편리 함수를 제공해준다.

operator 모듈에는 itemgetter(), attrgetter() 및 methodcaller() 함수가 있다.

이러한 함수를 사용하면, 위에서 했던 것들을 더 간단하고 빠르게 할 수 있다.

 

from operator import itemgetter, attrgetter

 

이렇게 호출한 뒤

 

sorted(student_tuples, key = itemgetter(2))
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

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

 

이렇게 사용한다.

함수 이름은 상당히 직관적이다. itemgetter(idx) : 이터레이터 객체의 idx번째 아이템을 기준으로 정렬한다.

dictionary를 dictionary.items() 형태로 만든 것에 key = itemgetter(1)를 사용할 경우 value 기준 정렬을 사용할 수 있다. 

 

a = {'dave':10, 'sam':5, 'eunha':15}
sorted(a.items(), key = itemgetter(1))
# [('sam', 5), ('dave', 10), ('eunha', 15)]

 

리스트 형식의 return이 마음에 들지 않는다면 딕셔너리 컴프리헨션을 이용하면 된다.

 

a = {'dave':10, 'sam':5, 'eunha':15}
{k:v for k, v in sorted(a.items(), key = itemgetter(1))}
# {'sam': 5, 'dave': 10, 'eunha': 15}

 

한편 operator 모듈 함수는 다중 수준의 정렬을 허용한다. 예를 들어, 먼저 grade로 정렬한 다음 age로 정렬하려면, 이렇게 한다.

 

sorted(student_tuples, key = itemgetter(1,2))
# [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

sorted(student_objects, key = attrgetter('grade', 'age'))
# [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

 

오름차순과 내림차순

list.sort()와 sorted()는 모두 boolean 값을 갖는 reverse 매개변수를 받아들인다.

reverse = False를 줄 경우 오름차순, reverse = True를 줄 경우 내림차순 정렬을 return 한다.

또, reverse 매개 변수는 여전히 정렬 안정성을 유지한다. (그래서 같은 키를 갖는 레코드는 원래 순서를 유지한다.)

이 효과는 내장 reversed() 함수를 두 번 사용하여 매개 변수 없이 흉내낼 수 있다.

정렬 안정성과 복잡한 정렬

정렬은 안정적임이 보장된다.

안정적이라는 뜻은 같은 값의 경우 원래의 순서가 유지된다는 뜻이다.

 

data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
sorted(data, key = itemgetter(0))
# [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

 

정렬의 키가 'blue'와 'blue'로 서로 같았지만 처음 나왔던 ('blue', 1)이 앞에 나오도록, 안정적인 정렬 결과가 리턴되었다.

복잡한 정렬에 유용하게 사용된다.

장식-정렬-복원을 사용하는 낡은 방법

이 관용구는 그것의 세 단계를 따라 장식-정렬-복원(Decorate-Sort-Undecorate)라고 한다.

1) 초기 리스트가 정렬 순서를 제어하는 새로운 값으로 장식된다.

2) 장식된 리스트를 정렬한다.

3) 장식을 제거하여, 새 순서로 초깃값만 포함하는 리스트를 만든다.

다음과 같다.

 

decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
decorated.sort()
[student for grade, i, student in decorated]
# [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

 

이 관용구는 튜플이 사전식으로 비교되기 때문에 안정적으로 작동한다.

사전식으로 비교된다 : 첫 번째 항목을 비교한 후에 같으면 두 번째 항목을 비교하여... 다른 값이 나오면 그것을 기반으로 정렬한다.

모든 경우에 장식된 리스트에 인덱스 i를 포함할 필요는 없지만, 두 가지 이점이 있다.

1) 정렬이 안정적이다 : 두 항목이 같은 키를 가지면, 그들의 순서가 정렬된 리스트에 유지된다.

2) 장식된 튜플의 순서는 최대 처음 두 항목에 의해 결정되므로 원래 항목은 비교 가능할 필요가 없다. 그래서 예를 들어, 원래 리스트에는 직접 정렬될 수 없는 복소수가 포함될 수 있다.

 

이 관용구의 또다른 이름은 펄 프로그래머들 사이에서 이것을 대중화한 Randal L. Schwartz의 이름을 딴 Schwartzian 변환이다.

이제 파이썬 정렬이 키 함수를 제공하기 때문에, 이 기법은 자주 필요하지 않다.