정렬 알고리즘의 종류
| 정렬 알고리즘 | 정의 |
|---|---|
| 버블(bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
| 선택(selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
| 삽입(insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
| 퀵(quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
| 병합(merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
| 기수(radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
그 중, 다른 정렬 알고리즘보다는 시간 복잡도(O(n^2))는 높지만 구현이 간단한 버블 정렬에 대해서 정리해보려고 한다.
정렬 과정
오름차순 정렬 과정을 버블 정렬 알고리즘으로 하게 된다면
- 인접한 2개의 값을 비교, 작은 값을 앞으로 교환(이미 작은 값이 앞에 있으면 교환 x)
- 가장 큰 수가 오른쪽 끝으로 이동하게 됨
- 1, 2의 과정을 반복
Key Point
- 버블 정렬의 핵심은 loop내에서 인접 데이터 간의 swap 연산
- 만약 특정 루프의 전체 영역에서 swap이 발생하지 않았다면, 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로 프로세스를 종료
적용해보기!
간단한 수 정렬문제를 버블 정렬 알고리즘을 사용하여 풀이해보았다
나의 개발로그