리스트 정렬하는 방법

리스트 정렬하기

파이썬의 리스트는 .sort() 메소드를 이용해서 정렬할 수 있다. 단, 이 때의 정렬은 제자리 정렬로, .sort() 메소드는 리턴값이 없으며 (리턴값이 없는 파이썬 함수가 늘 그러하듯None을 리턴하기는 한다.) 메소드를 호출한 원본 리스트의 내부 원소들이 순서를 바꾸게 된다.

실제로 메모리 사용량을 극히 제한해야 하는 특수한 상황이 아니라면 제자리 정렬보다는 sorted 함수를 이용한 정렬이 보다 안전하다. (제자리 정렬은 되돌릴 수가 없다.) sorted는 말 그대로 "정렬된" 사본을 만들어주는데, .sort()가 리스트 객체의 메소드라는 한계를 갖는데 비해, sorted함수는 "연속열"을 정렬하는 함수이기 때문에 튜플이나 그외의 반복자등의 연속열을 정렬된 리스트로 만들 수 있다.

In [61]: a = [5, 2, 8, 3, 7, 1, 9]

In [62]: sorted(a)
Out[62]: [1, 2, 3, 5, 7, 8, 9]

In [63]: b = (5, 3, 2)

In [64]: sorted(b)
Out[64]: [2, 3, 5]

In [65]: a
Out[65]: [5, 2, 8, 3, 7, 1, 9]

In [66]: b
Out[66]: (5, 3, 2)

역순으로 정렬하기

sorted() 함수에 대해 도움말을 찾아보면, 다음과 같은 내용을 볼 수 있다.

In [93]: sorted?
Signature: sorted(iterable, /, *, key=None, reverse=False)
Docstring:
Return a new list containing all items from the iterable in ascending order.

A custom key function can be supplied to customize the sort order, and the
reverse flag can be set to request the result in descending order.
Type:      builtin_function_or_method

key와 reverse라는 두 개의 키워드 인자가 보인다. reverse를 True로 두면 역순으로 정렬해준다.

정렬 조건 적용하기

정렬하고자 하는 연속열이 단순히 숫자값이나 문자열이라면 sorted 함수는 이를 크기순 혹은 사전순으로 정렬하여 그 결과를 리턴한다. 하지만 별도의 정렬 기준을 사용해야 할 필요가 있는 경우가 더 많을 것이다. 예를 들어,

• 어떤 학생의 정보를 보관하는 Student의 클래스 인스턴스의 리스트를 수학 성적 순으로 정렬하고 싶을 때
• 단어를 길이 순으로 정렬하고 싶을 때
• 어떤 정수의 리스트를 5로 나눈 나머지가 작은 순으로 정렬하고 싶을 때

같은 경우를 상정할 수 있다. 이 때 사용하는 것이 key= 파라미터이다. 이 파라미터에는 연속열의 각 원소를 받아서 정렬 기준이 되는 값을 리턴하는 함수가 올 수 있다.

#  예를 들어 여러 단어들이 있을 때, 이 단어들을 길이 순으로 정렬하고 싶다고 하자. 
# 한 단어의 길이는 기본함수 `len`에 의해서 구할 수 있다. 따라서, 
words = ...
sorted_by_length = sorted(words, key=len)

# 어떤 학생들의 리스트를 수학 점수가 높은 순으로 정렬하고 싶다면
# 다음과 같이 쓸 수 있다.
students = ...
names_sorted_by_math = [x.name for x in \
                        sorted(student, key=lambda x: x.math_score, reverse=True)]

key 파라미터는 함수를 받는 파라미터이기 때문에 기본적으로 람다식을 쓸 수 있다.

팁 : 두 개 이상의 정렬 조건을 사용하기

흔치 않은 경우이기는 한데, 가끔 두 개 이상의 정렬조건을 사용하고자 할 필요가 있는 경우가 있다. 예를 들어 어떤 단어들의 목록을 가지고 있을 때, 이 목록을 단어의 길이 순으로 정렬하는 것은 길이가 같은 단어들 사이의 정렬은 정의되지 않는다는 뜻이다. 만약 단어의 길이 순으로 정렬하면서, 같은 길이의 단어는 다시 사전순으로 정렬되어야 한다면 어떻게 정렬할 수 있을까?

바로 key 함수의 리턴값이 (첫번째기준, 두번째기준) 형식의 튜플이면 된다.

# 단어를 준비
In [99]: words = [x.strip('.,') for x in "Python has a very powerful tuple assignment feature that allows a tuple of variables on the left of an assignment to b
    ...: e assigned values from a tuple on the right of the assignment.".split()]

In [100]: words
Out[100]:
['Python',
 'has',
 'a',
 'very',
 'powerful',
 'tuple',
 'assignment',
 'feature',
 'that',
 'allows',
 'a',
 'tuple',
 'of',
 'variables',
 'on',
 'the',
 'left',
 'of',
 'an',
 'assignment',
 'to',
 'be',
 'assigned',
 'values',
 'from',
 'a',
 'tuple',
 'on',
 'the',
 'right',
 'of',
 'the',
 'assignment']


# 길이 순으로 정렬한다. 같은 길이 단어들이 반드시 정렬되지는 않는다.
In [101]: sorted(words, key=len)
Out[101]:
['a',
 'a',
 'a',
 'of',
 'on',
 'of',
 'an',
 'to',
 'be',
 'on',
 'of',
 'has',
 'the',
 'the',
 'the',
 'very',
 'that',
 'left',
 'from',
 'tuple',
 'tuple',
 'tuple',
 'right',
 'Python',
 'allows',
 'values',
 'feature',
 'powerful',
 'assigned',
 'variables',
 'assignment',
 'assignment',
 'assignment']

# 길이순으로 정렬하면서 같은 길이에서는 알파벳 순으로 정렬한다.
In [102]: sorted(words, key=lambda x: (len(x), x))
Out[102]:
['a',
 'a',
 'a',
 'an',
 'be',
 'of',
 'of',
 'of',
 'on',
 'on',
 'to',
 'has',
 'the',
 'the',
 'the',
 'from',
 'left',
 'that',
 'very',
 'right',
 'tuple',
 'tuple',
 'tuple',
 'Python',
 'allows',
 'values',
 'feature',
 'assigned',
 'powerful',
 'variables',
 'assignment',
 'assignment',
 'assignment']

사전의 내용을 정렬하기

기본적으로 사전 내부의 키-값 쌍은 순서를 가지지 않는다. 사전의 내용을 정렬한다는 것은 보통은 사전의 값을 키 혹은 값의 순서대로 정렬한 리스트를 만든다는 의미이다. (혹은 (키, 값)으로 구성된 튜플의 리스트가 될 수 있다.)

사전의 값만을 정렬하는 방법

사전의 값은 .values() 메소드를 통해서 얻을 수 있다. 이 값은 리스트가 아니지만 iterable 프로토콜을 따르고 있어서 sorted 함수를 통해서 정렬된 리스트로 만들 수 있다.

In [5]: d = dict(zip('rhgca', [4,2,1,5,7]))

In [6]: d.values()
Out[6]: dict_values([4, 2, 1, 5, 7])

In [7]: sorted(d.values())
Out[7]: [1, 2, 4, 5, 7]

사전의 값을 추출하여 정렬된 리스트로 만드는 것은 간단하다. 그런데 이 값들을 만약에 사전의 키 순으로 정렬하고 싶다면 어떻게할까? 리스트 축약 문법을 쓰면 간단히 처리할 수 있다. 대신에 여기에는 두 가지 접근법이 있을 수 있겠다.

사전의 키 순으로 정렬된 사전의 값들

사전의 키는 items() 메소드를 통해서 얻을 수 있으며, 이 역시 위와 같은 방식으로 정렬할 수 있다. 그리고 그 정렬된 키를 사전의 값으로 맵핑하면 된다. 따라서 다음과 같이 정렬된 키를 얻고, 각 키에 대응된 값으로 구성되는 리스트를 만들면 된다.

keys = sorted(d.items())
print([d[key] for key in keys])

혹은 .items()를 이용하는 방법이 있다. .items는 사전의 각 요소의 키-값 쌍인 튜플들을 리턴한다. 이 튜플에서 첫번째 요소인 키 순으로 정렬한 후, 두 번째 요소만 추려내는 것이다.

In [20]: items = d.items()

In [21]: [item[1] for item in sorted(items, key=lambda x: x[0])]
Out[21]: [7, 5, 1, 2, 4]

튜플의 리스트를 특정한 요소 기준으로 정렬하고자 할 때는 key 파라미터에 해당 요소를 리턴하는 함수를 주면 되므로 위와 같이 처리할 수 있다.

두 번째 방법은 튜플의 리스트를 어떤식으로 정렬할 수 있는지 보여주는 예이며, 두 방식을 비교했을 때는 전자가 더 빠르다. (후자는 그만큼 정렬함수의 동작이 복잡하기 때문이다.)

보너스

파이썬의 정렬은 내부적으로 팀정렬이라는 알고리듬을 사용한다. 흔히 퀵소트가 가장 빠른 정렬 알고리듬으로 알려져 있는데, 퀵소트의 단점은 정렬하고자 하는 대상 데이터가 정렬된 상태에 가까울 수록 효율이 떨어진다는 것이고, 보통 실제 데이터들은 완전히 뒤섞인 상태이기 보다는 부분적으로 정렬된 상태를 가지는 경우가 많다. 팀 정렬은 삽입 정렬과 개선된 합병 정렬을 조합하여 만들어진 알고리듬으로 팀 피터스에 의해서 파이썬의 정렬 알고리듬을 위해서 개발되었다.

팀정렬의 성능은 좋은 평가를 받아서 이후 Java 7등에도 이식되었다.