정렬의 안정성
1. Selection sort (L to R)
배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘
- 해당 배열의 첫번째 원소와 최솟값 원소 switch
장점
- 입력데이터에 덜 민감, 구현 쉬움
- 데이터 이동 최소 (linear 타임)
단점
- 이미 정렬된 데이터여도 quadratic time 요망 (多 비교 및 시간)
비용 분석
안정적이지 않다
- 동일한 숫자끼리 바뀜
2. Insertion sort (R to L)
- 해당배열의 마지막 원소를 왼쪽으로 이동하며 계속 switch
비용 분석
장점
- 최선의 경우 O(N)
- 성능 good, 다른 정렬의 일부로 활용
단점
- 최악의 경우, O(N^2)
- 데이터 상태에 따라 성능 차이
안정적이다
- 동일한 아이템으로 못넘어감. (같은거끼지 변경X)
3. Shell sort (삽입정렬 보완)
삽입정렬은 부분 정렬된 배열에 대해 빠르니, 이를 이용하면 ?!
: h-sorting 이용 !
- h를 반으로 줄여(반올림)가며 h=1이 될때까지 반복
비용 분석
- 배열의 크기가 아주 크지 않으면 매우 빠름
- 작은 사이즈의 코드로 구현 가능
안정적이지 않음
- 멀리 떨어져있는 요소를 교환해야함
4. Shuffling
Naive shuffle
균등분포를 가지도록 무작위 재배열하기 !
- 중복된 값 없어야 함
- 정렬 알고리즘 필요
Knuth shuffle
선형 시간 내 균등분포를 가지도록 무작위 재배열하기 !
5. Convex Hull
6. Merge sort
merge sort의 동작 방식
- 배열을 최소단위로 2등분
- 재귀적으로(recursively) 정렬한 후 합병
- 시작은 각 배열의 첫번째 원소끼리!
성능 분석 및 증명
경험적 분석
비교 횟수와 배열접근 횟수
- 추가적인 메모리 공간 필요
비용 분석
정렬의 복잡도
안정적임 (병합과정 안정적)
- 동일값 존재 시, 왼쪽 하위배열에 있는 값 먼저!
merge sort 응용
개선방안 1
- 이 정렬은 작은 부분 배열에 대해 성능이 안좋으므로, 16개 이하의 아이템을 가진 배열에 대해서는 insertion sort 를 사용
개선방안 2
- 이미 정렬되어 있다면, 실행중지
- 부분정렬된 배열에 대해 효과적
Bottom-up Merge Sort
- 전제 : 주어진 배열의 각 원소가 이진트리의 리프노드
- bottom(하위배열 사이즈가 1인 리프노드)에서 top (루트노드)로 배열 병합
개선방안 1
개선방안 1
c0d3_wh1t3