개요
정렬(Sorting)이란, 원소들을 일정한 순서대로 열거하는 알고리즘이다.1
이 정렬 알고리즘을 평가하는 효율성의 기준은 이하 2개가 있다.
- 비교 연산의 횟수
- 이동 연산의 횟수 이 두 횟수를 빅오 표기법을 이용해 근사적으로 표현한다.
분류
정렬 알고리즘은 대략 4가지 측면에 따라 분류할 수 있다.
1.
- 단순하지만 비효율적인 정렬: 삽입, 선택, 버블 정렬 등
- 복잡하지만 효율적인 정렬: 퀵, 힙(heap), 합병, 기수 정렬 등
2.
- 내부 정렬internal sorting: 정렬 전에 모든 데이터가 메인 메모리에 올라와있는 상태에서 정렬
- 외부 정렬external sorting: 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬
3.
- 안정 정렬: 입력 데이터에 동일한 키값을 갖는 레코드가 여러 개 존재할 경우, 이 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않는 정렬 ^bdbe64
- e.g.
- 정렬 전: [301, 302, 10, 20]
- 정렬 후: [10, 20, 301, 302]
- e.g.
- 비안정 정렬
4.
- 제자리 정렬in-placing sorting: 입력 배열 외에 추가 메모리를 요구하지 않는 정렬
- 비제자리 정렬