정렬..이란 말이죠...

정렬

정렬이란 주어진 데이터를 원하는 순서대로 재배열하는 연산이다.

왜 정렬을 하느냐. 왜 가만있는 데이터를 재배열하느냐.

 

예를 들어, 1000개의 데이터가 있을 때 정렬되지 않은 데이터 집단은 특정 데이터를 찾을 때 일일히 샅샅히 순차적으로 뒤져야 할 것이다. 꽤 중노동의 일이다.

 

하지만 데이터가 예쁘게 정렬된 집단인 경우 여러 탐색 방법을 통해 빨리 해당 데이터를 찾을 수 있을 것이다.

데이터를 원하는대로 이용하기 쉽게하기 위해, 정렬이 필요한 것이다.

정렬 시 요구되는 탐색 방법들을 알맞게, 똑똑하게 사용하는 것이 개발자의 역량이라 생각한다.

 

 

 

데이터 정렬 방법: 2가지

내부 정렬(internal sorting)

정렬한 데이터 집단 크기가 적당해 주기억 장치에서 정렬이 가능하다.

삽입 정렬, 선택 정렬, 버블 정렬, 쉘 정렬, 퀵 정렬, 2-원 합병 정렬, 히프 정렬, 기수 정렬 등

(교수님 왈, 히프 정렬은 가장 완벽한 정렬 알고리즘이라 하셨음)(왜인지는 힙 정렬 배울 때 알아보자)

 

외부 정렬(external sorting)

데이터 집단이 매우 클 때 보조 기억 장치(디스크, 자기 테이프 등)를 이용해 정렬하는 벙법이다.

자원 2-원 합병, 균형 2-원 합병, 균형 2-원 합병, 균형 m-원 합병, 다단계 합병 등 주로 합병에 대해 설명한다.

 

 

내부 정렬

입력 자료: 입력 데이터는 대부분 배열에 저장(일부는 연결리스트 사용)

A[1], A[2], ... , A[n]을 입력으로 봄 (간혹, 경우에 따라 A[0]를 포함하기도 함)