정렬이란?

· 크기 순서에 무관하게 나열된 데이터를 크기 순서대로 다시 나열하는 작업.

· 데이터를 탐색하는데 반드시 필요한 작업.

· 크기가 커지는 순서로 정렬 → 오름차순 정렬.

· 크기가 작아지는 순서로 정렬 → 내림차순 정렬.

정렬 알고리즘의 효율을 평가하는 기준

· 비교횟수

· 데이터의 이동횟수

· 사용되는 메모리의 양

내부 정렬이란?

레코드를 모두 메모리 안으로 읽어 들여 리스트를 정렬하는 것.

* 레코드 : 정렬해야 할 대상.

* 리스트 : 레코드의 집합.

내부 정렬 방법

· 기본 정렬 방법 : 삽입 정렬, 선택 정렬, 버블 정렬.

· 성능 개선 방법 : 퀵 정렬, 합병 정렬, 쉡 정렬, 힙 정렬, 기수 정렬. 

외부 정렬이란?

외부 기억장치에 있는 레코드의 집합인 파일을 대상으로 레코드를 정렬하는 것.

* 파일 : 외부(보조)기억장치에 저장되는 레코드의 집합.

내부 정렬과 외부 정렬의 비교

· 내부 정렬은 메모리 안에서 정렬이 이루어지기에 접근 속도가 빠른 반면 외부 정렬은 상대적으로 접근 속도가 매우 느림.

· 용량의 차이는 내부 정렬이 메모리를 사용하기에 외부 정렬보다 상대적으로 매우 적다.

· 내부 정렬에서 레코드들을 비교 및 이동하는데 걸리는 시간은 메모리 접근 빈도수에 비례, 외부 정렬에서는 블럭 위의 파일 접근 빈도수에 비례.

· 내부 정렬의 효율은 데이터의 비교나 이동횟수를 줄임으로써 향상, 외부 정렬은 파일 I/O 횟수를 줄이는 것이 정렬시간을 줄이는 역할.

[출처] 정렬 탐색 프로그래밍