정렬을 위한 알고리즘을 정리하려고 한다.
1. 선택 정렬: 큰(작은) 키 값을 찾아 교환한다.
2. 버블 정렬: 인접한 키 값을 교환하고, 이미 정렬돼있으면 중단한다.
3. 삽입 정렬: 자신의 위치를 찾아서 삽입한다.
4. 쉘 정렬: 좀 더 개선된 삽입 정렬이다.
5. 퀵 정렬: 자료의 중갑 값을 정한 후 정렬한다.
6. 힙 정렬: 이진 트리 구조를 만들어 정렬한다.
7. 이진 병합 정렬: 두 개의 키를 한 쌍으로 정한 후 정렬한다.
8. 버킷 정렬: 기수 값에 따라 분배하여 정렬한다.
시간 복잡도(Big-O 표기법 사용) 비교 - 최선 ~ 최악을 같이 표기함
삽입 정렬 - O(n ~ n^2)
버블 정렬, 선택 정렬 - O(n^2)
쉘 정렬 - O(n ~ n^1.5)
퀵 정렬 - O(nlog₂n ~ n^2)
힙 정렬, 이진 병합 정렬 - O(nlog₂n)
버킷 정렬 - O(dn) (d는 자릿수)
'👨🏫일문일답' 카테고리의 다른 글
[20210924] 절차적 프로그래밍과 객체 지향 프로그래밍 (0) | 2021.09.24 |
---|---|
[20210917] 프로세스, 스레드 차이(+ 멀티 프로세싱, 멀티 스레딩) (0) | 2021.09.18 |
[20210904] 인터페이스와 추상 클래스의 차이 (0) | 2021.09.14 |
[20210913] 객체지향 특성 - 클래스, 객체, 상속, 캡슐화, 추상화, 다형성 (0) | 2021.09.13 |
[20210906] 검색 알고리즘 (0) | 2021.09.06 |