Python 74 - 정렬 _ 기준에 따라 데이터를 정렬 (정렬 라이브러리)

정렬 라이브러리

알고리즘은 오랫동안 연구된 분야이며, 특히 정렬 알고리즘은 매우 많이 연구된 주체이다. 그렇기 떄문에 정렬 알고리즘은 이 밖에도 매우 다양한 종류가 있다. 물론, 현대의 정렬 알고리즘은 정립되어 있기 때문에 앞으로는 큰 개선이 이루어질 것으로 예상하기는 어렵다. 따라서 정렬 알고리즘 문제는 어느정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있다.

지금까지 다양한 정렬 알고리즘에 대해서 알아보았다. 우리가 알고리즘 문제를 풀 때는 앞서 다루었던 에제처럼 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 더 많다.

 

파이썬은 기본 정렬 라이브러리인 Sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만, 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. 이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

sorted 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

출력결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다. 리스트 객체의 내장 함수인 sort()를 이용하는 것인데, 이를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

sort소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

array.sort()
print(array)

출력결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

또한 sorted()나 sort()를 이용할 때에는 key매개변수를 입력으로 받을 수 있다. key값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다. 예를 들어 리스트의 데이터가 튜플로 구성되어 있을 때, 각 데이터의 두 번쨰 원소를 기준으로 설정하는 경우 다음과 같은 형태의 소스코드를 작성할 수 있다. 혹은 람다(lamda)함수를 사용할 수도 있다.

정렬 라이브러리에서 key를 활용한 소스코드

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]
result = sorted(array, key=setting)
print(result)

출력결과
[('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 사실 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 더욱더 효과적이다. 앞서 파이썬은 병합 정렬에 기반한다고 했는데 정확히는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용한다. 책에서 자세히 다루지는 않지만, 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정 되어있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.

1. 정렬 라이브러리 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

이 책에서는 이 3가지 유형을 모두 다룰 것이다. 일단 다음 글에서부터는 가장 기본적인 문제 3개를 풀어보도록 하자.

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding