🎞️ Bubble Sort - O(n^2)
특징
- 크기 작은 배열에 적합
- O(1) 공간복잡도
- stable
과정
- 첫 원소부터 시작해서 다음 원소와 비교하여 swap
- 다시 처음부터 하나씩 비교하며 swap
- 더이상 swap할게 없을 때까지 반복
🎞️ Selection Sort - O(n^2)
특징
- 작은 배열에 적합
- O(1) 공간 복잡도
- 가장 작은 원소를 찾아 첫 인덱스의 값과 swap
- 배열에 sorted 부분과 unsorted 부분이 존재하는데, 매번 unsorted 부분에서 가장 작은 원소를 찾아 sorted 부분의 끝+1 인덱스에 swap
🎞️ Insertion Sort - O(n^2)
특징
- 작은 배열에 적합
- O(1) 공간 복잡도
- 부분적으로 정렬된 배열에 적합
- stable
과정
- 첫 원소와 둘째 원소부터 비교하여 swap
- 특정 원소 차례일 때 이 원소보다 작은 값만 이 원소 앞에 존재할 때까지 swap
🎞️ Merge Sort - O(n log n)
배열을 쪼개고 쪼개서 정렬하고 다시 합치기
- 서브 배열의 크기가 1이 될때까지 재귀적으로 배열을 쪼갬
- 서브 배열의 크기가 1이 되면 재귀적으로 merge 과정을 시작하는데, 각 서브배열의 값을 비교하여 합침
🎞️ Quick Sort - O(n log n)
Pivot 원소를 기준으로 배열을 쪼갬
Pivot 고르는 방법
- 첫 원소 선택
- 마지막 원소 선택
- 랜덤하게 선택
- 중앙값 선택
과정
- pivot 선택
- pivot을 제외하고 pivot보다 작은 값이 든 배열과 pivot보다 큰 값이 든 배열로 쪼갬
- 각 배열의 크기가 1 이하일 때까지 쪼갬
- 합치기
🎞️ Radix Sort
낮은 자릿수부터 비교하여 정렬함
- 0~9까지의 queue 자료구조의 버킷을 준비함
- 모든 데이터에 대해 가장 낮은 자리수에 해당하는 버킷에 위치 (54는 4 큐에 위치)
- 0부터 차례대로 버킷에서 데이터를 다시 가져옴
- 자리수를 높여가며 2~3 반복
🎞️ Quick Sort vs. Merge Sort
Quick sort
- 최악의 경우: Pivot(기준) 요소가 항상 유일한 최소/최대 원소일 경우
- 시간복잡도
- 최선: O(n log n)
- 최악: O(n^2)
- 메모리가 부족한 경우 (병합정렬 사용 불가)
- 배열이 정렬/역정렬되어 있지 않는 경우 (최악 성능 냄)
Merge Sort
- 메모리가 충분할 경우 적합
- LinkedList 정렬에 효율적임
- 순차적인 비교를 통해 정렬
- 메모리 효율이 중요하면 쓰면 안됨
Quick Sort vs. Merge Sort
- 부분 배열
- 퀵정렬: 나뉜 배열은 여러 비율
- 병합 정렬: 배열은 항상 반으로
- 최악의 경우 시간 복잡도
- 퀵정렬: O(n^2)
- 병합정렬: O(n log n)
- 사용 용도
- 퀵정렬: 작은 크기의 배열에 적합
- 병합정렬: 크기와는 무관
- 정렬방식
- 퀵정렬: 내부 정렬
- 병합정렬: 외부 정렬
- 별도 저장 공간
- 퀵정렬: 불필요
- 병합정렬: 필요
- 메모리 사용
- 퀵정렬: tail recursive해서 tail call optimization이 적용됨 > 메모리 공간 사용 최적화
- tail recursive: 재귀함수 중 재귀호출이 함수의 가장 마지막 줄에 수행되는 것
- tail call optimization
- tail recursive하지 않는 함수에서는 함수의 실행 중에 다른 함수가 실행되면 이전 함수의 정보를 유지해야 함
- tail recursive하면 함수의 마지막에서 호출된 거라 이전 함수의 값은 나중에 리턴을 위해 결과만 저장하면 됨
- 퀵정렬: tail recursive해서 tail call optimization이 적용됨 > 메모리 공간 사용 최적화
- 참조지역성 관점에서 퀵정렬이 병합정렬보다 빠름 (배열일 경우 더 효과적)
- 자주 사용되는 page는 물리 메모리랑 캐시 모두에 두는데, 지역성의 원리에 따라 hit율이 높다면 캐시에 해당 페이지를 자주 접근하게 되어 성능이 올라감
- 퀵 정렬은 병합 정렬보다 더 빠르게 주변 데이터 접근함 > 속도가 일반적으로 더 빠름
🎞️ Quick Sort에서 O(N^2) 걸리는 이유와 개선 방법
항상 가장 불리한 pivot을 선택하면 O(N^2) 시간복잡도를 얻을 수 있음
(예) 이미 정렬된 배열에서 유일한 최소/최댓값 선택
개선방안
- Pivot으로 최소/최댓값을 선택하지 않고 랜덤하게 선택하거나 중앙값을 선택하면 정렬된 배열에서도 최악의 시간복잡도는 면할 수 있음
- 삽입정렬과 함께 사용
- 삽입 정렬은:
- 추가 메모리를 필요로 하지 않음
- 크기가 작은 배열에서 매우 좋은 효율
- 구현이 간단함
- 작은 배열은 삽입 정렬으로 퀵 정렬의 재귀의 깊이 줄임 > 속도 향상
- 조건으로 삽입 정렬과 퀵 정렬 케이스 나누기
- 삽입 정렬은:
🎞️ Stable Sort
Stable Sort(안정 정렬): 중복된 키를 순서대로 정렬하는 알고리즘
Stable Sort: Insertion sort, Merge sort, Bubble sort, Counting sort
Unstable Sort: Selection sort, Heap sort, Shell sort, Quick sort
🎞️ 비재귀 Merge Sort
가능은한데 구현이 복잡하고 길어져서 굳이?
🎞️ Bubble, Selection, Insertion Sort의 속도 비교
Bubble Sort
- worst: O(n^2)
- average: O(n^2)
- best: O(n)
- 정렬된 배열인 경우
Selection Sort
- worst: O(n^2)
- average: O(n^2)
- best: O(n^2)
Insertion Sort
- worst: O(n^2)
- average: O(n^2)
- best: O(n)
- 정렬된 배열인 경우
값이 거의 정렬되어 있거나, 아예 정렬되어 있는 경우의 성능 비교
부분적으로 정렬된 배열
- selection sort과 bubble sort는 부분적으로 정렬된 배열에 최적화되있지 않음
- insertion sort은 부분적으로 정렬된 배열에 매우 적합함
아예 정렬 된 배열에서는 모든 sort가 편리함
🎞️ Java의 Sort
Java의 Collections.sort() 메서드 - Merge Sort
🎞️ 정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면 정렬 방식
삽입 정렬과 퀵정렬의 조합
일정 크기보다 큰 배열은 퀵정렬
작으면 삽입정렬
참고:
우당탕탕