10-1 정렬의 의미

정렬: 우리가 데이터를 저장하기 위해 복잡한 자료구조를 사용하는 이유는, 대부분의 경우 효율적인 탐색과 정렬을 위함. 탐색은 많은 자료 중 무언가를 찾는 작업, 정렬은 데이터를 순서대로 재배열하는 것을 말함.

 

정렬을 위해서는 사물을 서로 비교할 수 있어야 함. 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있다.

기준의 예시로는 오름차순, 내림차순, 알파벳 순 등이 있다.

 

정렬시켜야 될 대상은 레코드라 부르고 레코드는 여러 개의 필드로 이뤄진다.

ex) 경주마의 경우 번호, 이름 키 등의 다양한 속성이 필드가 됨.

이들 중 정렬의 기준이 되는 필드를 key 또는 sort key라 한다. 정렬이란 레코드들을 키의 순서로 재배열하는 것임.

 

정렬 장소에 따른 분류

내부(internal) 정렬: 모든 데이터가 메인 메모리에 올라와 있는 정렬을 의미한다.

외부(external)정렬: 외부 기억 장치에 대부분의 데이터가 있고 일부 메모리에 올려 정렬하는 방법. (대용량 자료 정렬)

 

구현 복잡도와 알고리즘의 효율성에 따른 분류

단순하지만 비효율적: 삽입정렬, 선택정렬, 버블정렬 등...

복잡하지만 효율적: 퀵 정렬, 힙 정렬, 병합정렬, 기수정렬 등...

 

안정성에 따른 분류: 입력 데이터에 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것을 말함.