-
정렬이란
n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다.
- 정렬의 종류
정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다.
- 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, Ο(n²)
- 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, Ο(n²)
- 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, Ο(nlogn)
- 퀵 정렬 특정 값을 기준으로 영역을 나누어 자리를 바꾸는 연산을 반복하는 정렬, Ο(nlogn)
- 힙 정렬 최대 힙 또는 최소 힙을 생성하여 원소를 삽입하고 인출하는 정렬, Ο(nlogn)
※ 퀵 정렬이 평균적인 성능이 좋기 때문에 많이 사용된다.