[CH6 정렬] 기준에 따라 데이터를 정렬 (6)

정렬 알고리즘 비교하기

지금까지 다룬 알고리즘을 비교하면 이와 같다

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단하다
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때는 가장 빠르다
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠르다
계수 정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다

추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다!

그러니까 코테에선 왠만하면 라이브러리 정렬 함수 사용하자~

 

---

파이썬의 정렬 라이브러리

알고리즘은 오랫동안 연구된 분야이고, 특히 정렬 알고리즘은 매우 많이 연구된 주제이다

그래서 정렬 알고리즘은 매우 다양한 종류가 있지만, 앞으로의 큰 개선이 예상되지는 않는다

따라서 정렬 알고리즘 문제는 어느정도 답이 정해진, 외워서 잘 풀리는 문제라고 할 수 있다!

 

파이썬에서는 sorted함수와 sort함수를 기본 라이브러리로 제공한다

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

result = sorted(list) #sorted 함수
list.sort() #sort 함수

 

 

또한 sorted( )나 sort( )를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다

key값으로는 하나의 함수가 들어가야 하며, 이는 정렬 기준이 된다

array = [("바나나", 2), ("apple", 5), ("onion", 3)]

def setting(data):
	return data[1]

result = sorted(array, key=setting)
print(result) 

#result -> [("바나나", 2), ("onion", 3), ("apple", 5)]

위처럼 하면 array의 두번째 원소가 정렬 기준이 되는 것이다!

 

 

---

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

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다

사실 정렬 라이브러리는 이미 잘 작성된 함수라 직접 퀵 정렬을 구현하는 것보다 효율적이다

 

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

1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
3. 더 빠른 정렬이 필요한 문제

이제 다음에서 위의 3가지 유형의 문제를 모두 풀어보자!