정렬이란?
- 순서 없이 배열되어 있는 자료들을 정해진 순서대로 가지런하게 나열하는 것을 의미한다.
정렬의 필요성
- 데이터를 정렬해야 하는 가장 큰 이유는 탐색을 위해서이다.
- 컴퓨터가 다뤄야 할 데이터는 보통 백만 개 단위이며, 데이터베이스는 이론상 무한 개의 데이터를 다룰 수 있어야 한다.
- 탐색 할 대상의 데이터가 정렬되어 있지 않다면 순차 탐색 외에 다른 알고리즘을 사용할 수 없다.
- 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다.
(여기서 시간 복잡도를 따지게 되는데, 이것에 대해서는 차후 포스팅함)
오름차순(Ascending) 내림차순(Descending)
- 나열하는 순서에 따라서 오름차순과 내림차순으로 구분한다.
- 오름차순은 1 - 2 - 3 - 4 ... 와 같이 뒤로 갈수록 숫자가 커지는 경우이고 내림차순은 그 반대이다.
- 정렬한 결과물을 선그래프로 그렸을 때 값이 작은 것을 앞으로 정렬하면 그래프의 선이 ↗올라가므로 오름차순이다.
- 값이 큰 것을 앞으로 정렬하면 그래프의 선이 ↘내려가므로 내림차순이라고 생각하면 쉽게 외울 수 있다.
- 어휘의 순서를 기반으로 한 정렬도 ABC, 또는 ㄱㄴㄷ 처럼 사전식으로 나열하는 경우를 오름차순이라고 한다.
key
- 자료를 정렬하는데 사용하는 기준이 되는 특정 값을 키(key)라고 한다.
- 여러가지 데이터가 모인 표나 DB같은 경우 데이터들을 정렬할 때 기준이 되는 값이다.
- 학생들의 성적을 입력한 데이터 시트에서 첫 번째 기준을 총점, 두 번째 기준을 학년, 세 번째 기준을 학번으로 하여 정렬하면 세 개의 키를 사용한 정렬이 된다.
정렬 방법의 분류
- 정렬 방법은 실행하는 방법과 정렬이 수행되는 장소에 따라서 분류할 수 있다.
실행 방법에 따른 분류
- 비교식 정렬
: 비교할 각 키값들을 한 번에 2개씩 비교하여 교환함으로써 정렬을 실행하는 방식이다.
- 분산식 정렬
: 키값을 기준으로 하여 자료를 여러 개의 부분집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식이다.
정렬 장소에 따른 분류
- 내부 정렬
: 정렬할 자료는 메인 메모리에 올려서 정렬하는 방식이다.
: 정렬 속도는 빠르지만, 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된다는 단점이 있다.
- 교환 방식 : 키를 비교하고 교환하여 정렬 (선택 정렬, 버블 정렬, 퀵 정렬)
- 삽입 방식 : 키를 비교하고 삽입하여 정렬 (삽입 정렬, 셸 정렬)
- 병합 방식 : 키를 비교하고 병합하여 정렬 (2-way병합, n-way병합)
- 분배 방식 : 키를 구성하는 값을 여러개의 부분집합에 분배하여 정렬 (기수 정렬)
- 선택 방식 : 이진트리를 사용하여 정렬 (힙 정렬, 트리정렬)
- 외부 정렬
: 대용량의 보조 기억장치를 사용하는 방식이다.
: 내부 정렬보다 속도는 떨어지지만, 내부 정렬로 처리할 수 없는 대용량의 자료를 정렬할 수 있다.
덧글