1. 소개
: 리스트의 항목들을 특정한 순서에 따라 재배치
⭐정렬 알고리즘의 분류
a. 내부정렬 vs 외부정렬
- 내부 정렬
: 정렬할 모든 데이터를 "메모리 내" 에서 정렬
- 외부 정렬 : 정렬할 데이터가 메모리 크기보다 클 때, 디스크와 같은 보조메모리를 사용해 일부 메모리만을 주 메모리로 가져와 정렬을 하는 것
(ex : 컴퓨터의 주기억 장치의 용량이 1GB이고, 정렬할 입력의 크기가 100GB이면, 어떤 내부정렬 알고리즘으로도 정렬할 수 없다. )
-
외부 정렬은 전체 데이터를 보조 기억장치에 저장 후, 주기억장치에 수용 가능한 크기만큼 작은 묶음으로 전달합니다.
-
그 후 주기억장치에서 작은 묶음에 대해 내부 정렬(예: 퀵소트, 병합소트 등)을 수행하고, 해당 결과를 다시 보조 기억장치(하드 디스크, SSD 등)에 저장합니다.
-
보조기억장치들의 정렬된 작은 묶음들을 다시 주 메모리로 가져와 합병정렬(merge sort)를 통해 하나의 블록으로 합친다.
주 메모리와 보조 메모리 사이의 작업 분배 이유?
< 주 메모리에서의 정렬 과정 >
주 메모리에서의 정렬은 일반적으로 빠르고 효율적입니다. 주 메모리에 데이터를 로드하고 정렬하면 접근 속도가 매우 빠르기 때문입니다. 따라서, 주 메모리에 로드된 작은 데이터 묶음을 효율적으로 정렬할 수 있습니다.
< 보조 메모리에서의 정렬 과정 >
반면에 보조 메모리에서의 정렬은 주 메모리에 비해 접근 속도가 느립니다. 하드 디스크나 SSD 같은 보조 메모리는 주 메모리보다 느린 속도로 데이터에 접근합니다. 따라서, 보조 메모리에서 데이터를 정렬하는 과정은 상대적으로 느릴 수 있습니다.
( -> 보조기억 장치의 접근시간은 느리기에, 보조 기억 장치에서의 읽고 쓰기를 최소화하는 것이 중요하다.)
: 예를 들어, 100GB의 데이터를 1GB만큼씩 주기억 장치로 읽어 들이고, 퀵 정렬과 같은 내부정렬 알고리즘을 이용하여 정렬, 이 후, 다른 보조 기억 장치에 저장한다.
이것을 반복하면 원래의 입력 100GB가 100개씩 정렬된 블록으로 분할되어 보조 기억 장치에 저장된다.
이제 정렬된 100개의 1gb 블록들을 다시 하나의 블록으로 병합정렬을 통해 만들어주면 된다
아래는 1gb 블록들을 2gb의 블록으로 병합정렬을 해주는 과정이다.
나머지 98개의 블록에 대해서 위 과정을 49회 추가로 반복하면, 2GB 블록 50개가 만들어진다.
그 다음에는 2GB 블록 2개씩 짝을 지워 합병시키는 과정을 25회 반복하여, 4GB 블록 25개가 만들어진다.
이러한 방식으로 계속 합병을 진행하면, 블록 크기가 2배씩 커지고, 블록의 수는 1/2씩 줄어들어 결국 100GB 블록 1개만 남는다.
b. 비교기반 정렬 vs 선형 정렬
<비교기반정렬>
: 비교 기반 정렬은 원소들 간의 상대적 크기를 비교하는 비교 연산을 사용하여 정렬을 수행합니다.대표적 알고리즘
: 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 등
<선형 정렬>
: 원소들의 상대적인 크기를 직접 비교하지 않는다는 것을 의미.
( 예를 들어 배열 속 원소의 갯수를 세어 정렬하는 redix Sort 등이 있음 )
대표적 알고리즘
: 계수 정렬(Counting Sort), 기수 정렬(Radix Sort), 버킷 정렬(Bucket Sort) 등.
선형 정렬 알고리즘은 특수한 경우, 비교 기반 정렬보다 빠른 시간 복잡도를 가지며, 특히 입력 데이터의 특성이 일정한 경우에 매우 효율적이다.
logN : 어떤 숫자 N에서 반복하여 2로 나누는 과정을 반복할 때, 최종적으로 1이 되는데 필요한 단계의 수!
