정렬 Algorithm
정렬 알고리즘의 종류
- 선택 정렬(Selection sort)
- 삽입 정렬(Insertion sort)
- 빠른 정렬(Quick sort)
- 계수 정렬(Counting sort)
1. 선택 정렬(Selection Sort)
- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞의 데이터와 교체
https://dev-lagom.tistory.com/37 - 시간 복잡도 O(N^2)
2. 삽입 정렬(Insertion Sort)
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
- 선택정렬보다 일반적으로 효율적
https://marobiana.tistory.com/85 - 시간 복잡도 O(N^2)
❗현재 리스트가 거의 정렬되어 있으면 매우 빠르게 동작 O(N)
3. 빠른 정렬(Quick Sort)
- 기준 데이터(pivot)을 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 자주 사용
- 병합 정렬과 더불어 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 정렬 방법
https://velog.io/@yaincoding/퀵-정렬Quick-Sort - 빠른 정렬이 빠른 이유
- 데이터의 분할이 절반에 가깝게 일어난다면 O(NlogN)의 시간 복잡도를 기대할 수 있기 때문!
- 데이터가 이미 정렬된 경우가 최악의 경우이며 이 때 시간 복잡도는 O(N^2)
4. 계수 정렬(Counting Sort)
- 데이터의 크기 범위가 제한되어 정수 형태로 표현되어 있을 때의 조건에 부합할 때만 사용할 수 있지만 빠르다
- 데이터의 개수 N, 데이터(양수) 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)
- 공간 복잡도는 최댓값이 커짐에 따라 커질 수 있으나 시간이 빠름, 공간 복잡도도 동일하게 O(N+K)
- 동일한 값을 가지는 데이터가 다수 등장할 때 효과적으로 사용될 수 있음
https://latte-is-horse.tistory.com/198
초보 개발자