[lecture] 6주차.정렬 알고리즘

내부 정렬(Internal sort)

내부 정렬이란 입력의 크기가 주기억 장치보다 크지 않은 경우에 수행하는 정렬이다. 예시로서는 버블, 선택, 삽입, 퀵, 힙, 쉘, 기수, 이중 피복 퀵, Tim sort 등이 있다.

외부 정렬(External sort)

내부 정렬과 반대로 외부 정렬은 보조 기억 장치에 있는 입력을 여러 번에 나눠 주기억장치에 읽어들인 후, 정렬해 보조 기억 장치에 다시 저장한다. 외부 정렬에는 다방향 합병(p-way Merge)과 다단계 합병(Polyphase Merge)이 있다.