성장일기
정렬 알고리즘 종류 & 장단점 본문
✨참고
[알고리즘] 각 정렬 알고리즘 비교 📝
비교 표 출처 : \[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도비교 표 출처 : \[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도" 인접 값끼리 비교하며 정렬. i를 length-i-1까지 올리는 정렬 "구현
velog.io
http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html
Eunji Kim @ CAU - 파이썬으로 정렬 알고리즘 구현하기
탐색과 정렬 알고리즘은 서로 뗄레야 뗄 수 없는 사이다. 원하는 값을 찾을 때까지 값을 차례로 살펴보는 순차탐색(sequential search)은 데이터가 정렬되어 있지 않아도 사용할 수 있지만 $O(n)$이다.
ejklike.github.io
https://coding-factory.tistory.com/615?category=794828
[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도
정렬 별 특징 선택정렬 (Selection Sort) 선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하
coding-factory.tistory.com
| 이름 | 최선 | 평균 | 최악 |
| 선택 정렬 | O(n2) | O(n2) | O(n2) |
| 버블 정렬 | O(n2) | O(n2) | O(n2) |
| 삽입 정렬 | O(n) | O(n) | O(n2) |
| 합병 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n2) |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) |
| 쉘 정렬 | O(N^1.25) | O(N^1.25) | O(N^1.25) |
| 기수 정렬 | O(dn) | O(dn) | O(dn) |
🎈장단점
1. 선택정렬
장점: 구현이 간단하다, 비교 횟수에 비해 교환이 적게 일어난다
단점: 정렬 시간이 오래 걸린다
2. 버블정렬
장점: 구현이 간단하다
단점: 정렬 시간이 오래 걸린다
3. 삽입 정렬
장점: 최선의 경우 O(n)으로 정렬 가능하다
단점: 최악의 경우 O(n2)이 걸린다
4. 합병 정렬
장점: 항상 O(nlogn)으로 일정한 속도로 정렬한다
단점: 추가적인 메모리 공간이 필요하다
5. 퀵 정렬
장점: 평균 실행시간이 O(nlogn)으로 빠른편이다.
단점: Pivot에 따라 성능 차이가 심하다, 최악의 경우 O(N2)
6. 힙 정렬
장점: 항상 O(nlogn)으로 빠른편이다.
단점: 다른 O(nlogn) 정렬법보다 오래걸린다.
7. 쉘 정렬
장점: O(nlogn)의 정렬법보다 빠르다
단점: 설정 간격에 따라 성능 차이가 심하다
8. 기수 정렬
장점: O(n)의 속도로 굉장히 빨리 정렬할 수 있다
단점: 추가적인 데이터가 굉장히 많이 필요, 데이터 타입 일정해야, 구현을 위한 조건이 많이 필요
'알고리즘' 카테고리의 다른 글
| 정렬 - 병합 정렬(merge sort) (0) | 2022.02.09 |
|---|---|
| 정렬 - 선택 정렬(selection sort) (0) | 2022.02.08 |
| 정렬 - 삽입 정렬(insertion sort) (0) | 2022.02.08 |
| 정렬 - 버블 정렬(bubble sort) (0) | 2022.02.08 |
| 유클리드 호제법 (0) | 2022.01.14 |