정렬 알고리즘의 종류
| 정렬 알고리즘 | 정의 |
|---|---|
| 버블(bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
| 선택(selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
| 삽입(insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
| 퀵(quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
| 병합(merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
| 기수(radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
선택 정렬 알고리즘은 버블 정렬과 같은 높은 시간 복잡도(O(n^2))를 가지고 있고 구현은 더 복잡하다 그래서 자주 사용하지 않는다고 한다.
정렬 과정
선택 정렬 알고리즘의 정렬 과정은 아래와 같다.
- 정렬 조건에 따라 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap
- 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다.
- 전체 데이터 크기만큼 index가 커질때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.
Key Point
- 선택 정렬의 핵심은 loop내에서 현재 인덱스의 데이터와 최대 또는 최소값 간의 swap 연산
적용해보기!
백준 온라인 저지 문제를 선택 정렬 알고리즘을 사용하여 풀이해보았다
나의 개발로그