시간복잡도에 따른 정렬분류
O(n²)
-
버블정렬(bubble sort)
인접한 인덱스끼리 비교하며 swap하여 큰 값부터 뒤로 쌓는다. -
선택정렬(selection sort)
남은 값 중에서 가장 작은 값을 탐색하여 앞으로 쌓는다. -
삽입정렬(insert sort)
모든 요소를 앞부분에 이미 정렬된 배열부분과 비교하여 자신의 위치를 찾아 삽입한다.
O(nlogn)
-
퀵정렬(quick sort)
1️⃣pivot을 기준으로 pivot보다 작은 데이터와 pivot보다 큰 데이터로 구분하고 그 사이에 pivot을 위치시킨다.
2️⃣pivot보다 작은 부분 / pivot보다 큰 부분에서 각각 재귀적으로 1️⃣을 다시 수행한다. -
힙정렬(heap sort)
힙 자료구조로 만들고 최상위 노드를 하나씩 뺀다. -
트리정렬(tree sort)
이진 탐색 트리(left child < parent < right child 로 정렬된 트리) 구조로 만들고
left child - parent - right child 순으로 순회한다. (=중위순회, LVR순회) -
병합정렬
다 쪼갬 - 쪼갠애들중에 제일 앞 인덱스끼리 정렬하면서 병합
하이브리드 정렬(두가지 이상의 정렬을 쓰까놓은 것)
- 팀정렬(tim sort)
병합정렬 + 삽입정렬Q.삽입정렬은 O(n²)인데 섞으면 더 구려지는거 아닌가?
삽입정렬은 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 잘 만족하므로 전체를 작은 덩어리로 잘라 각각을 삽입정렬한 뒤 병합정렬하면 빠르다고 한다. - 인트로정렬(intro sort)
퀵정렬 + 힙정렬
정렬 특징 요약
Q. 안정, 불안정?
같은 값을 정렬하는 경우 처음의 순서를 보장하는 정렬을 안정(stable)하다고 한다.
Q. tim sort는 안정할까 불안정할까?
tim sort는 병합(stable) + 삽입(stable) 이므로 역시 안정(stable)하다.
Q. O(nlogn)인 힙정렬이 O(nlogn ~ n²)인 퀵정렬보다 빠를까?
일반적으로 퀵정렬이 더 빠른데 그 이유
1. 퀵정렬은 평균 O(nlogn) 정렬중에 상수값이 가장 작다.
2. 힙 구조보다 배열구조가 원소끼리 인접 해 있기때문에 메모리상에서 참조하는 시간이 적게 든다.
3. 퀵정렬에서 pivot 선택 전략에서 어느정도의 휴리스틱을 가미하여 최악의 경우를 피할 수 있다.
내가 쓰는 언어의 빌트인 정렬은?
| 정렬 | 언어 |
|---|---|
| tim sort | python, Java SE 7, Android, Google chrome(v8), switft |
| intro sort | C++(표준은 아님), C# |
| 브라우저 엔진마다 다름 | js |
Q. 보통 내장 sort 쓰니까 정렬을 직접 구현하라고 하진 않을텐데... 각 정렬마다 원리를 알 필요가 있을까 ??
정렬 알고리즘에서 사용되는 테크닉이 다른 문제 풀이에 응용될 수 있다. ex) 분할정복
사용자 정의 정렬
파이썬
- lambda 표현식 사용
array.sort(key=lambda x : x[0]) # 첫번째 요소를 기준으로 내림차순 정렬
array.sort(key=lambda x : -x[1]) # 두번째 요소를 기준으로 오름차순 정렬
array.sort(key=lambda x : (x[0], x[1])) # 첫번째 요소를 기준으로 내림차순 정렬하고, 같은 겨우 두번째 요소로 내림차순 정렬
array.sort(key=lambda x : -sum([i for i,j in x])) # 원소 내의 첫번째 요소들의 합을 기준으로 오름차순 정렬- cmp_to_key 함수 사용
from functools import cmp_to_key
def compare(a, b):
return a - b # 양수일때 swap
array.sort(key=cmp_to_key(compare))자바스크립트
- compare 함수 정의하여 사용
funtion compare(a,b){
return a - b
}
array.sort(compare)