정렬이란?
엑셀이나 문서작성 프로그램을 사용한 사람이라면 데이터를 오름차순 혹은 내림차순으로 정렬 해본적이 있을 것이다.
정렬이란 데이터의 집합을 어떠한 기준(핵심항목, key)의 대소관계를 따져 일정한 순서로 줄지어 세우는 것이다.
또 하나의 예로는 국어사전, 영어사전같은 사전을 떠올릴 수 있겠다.
사전을 보면 알파벳 순서로 구성이 되어있지 않는가?
오름차순 : 기준값이 작은 데이터부터 큰 데이터 순으로 나열
ex) 1 2 3 4 5 6 7 ....
내림차순 : 오름차순의 반대
ex) 6 5 4 3 2 1
정렬 알고리즘의 안정성
예시를 들어 바로 설명을 해보겠다.
아직 정렬되지 않은 원본 데이터 집단이 있다.
같은 값을 가지는 3을 편의상 구분하기 위해 L과 R을 붙였다.
1, 4, 3(L), 2, 3(R), 7, 5
만약 오름차순으로 정렬을 한다고 가정하였을 때,
안정된 정렬 알고리즘의 경우 다음과 같이 정렬된다.
1, 2, 3(L), 3(R), 4, 5, 7
원본 데이터에서 같은 값을 가진 데이터는 순서가 원본 데이터와 동일하다.
안정되지 않은 알고리즘의 경우 정렬 결과는 다음과 같다.
1, 2, 3(R), 3(L), 4, 5, 7
같은 값을 가진 3의 순서가 바뀔 수 있다. 물론! 안바뀔 수도 있지만 안정된 알고리즘 처럼 확실하게 안바뀐다고 말을 할 수 없기때문에 안정되지 않다고 정의한다.
내부 정렬과 외부 정렬
- 내부정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용
- 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우
외부 정렬은 결국 내부 정렬을 응용한 것으로 외부정렬을 구현하기 위해선 작업을 위한 파일 등 처리를 따로 해주어야 한다. 앞으로 다루는 모든 정렬알고리즘은 모두 내부정렬이다.
정렬 알고리즘의 핵심요소
- 교환
- 선택
- 삽입
정렬알고리즘은 대부분 이 세가지 요소를 응용한다.
