[Algorithm] 정렬 알고리즘,내부정렬, 외부정렬

■ 정렬 알고리즘

여러 알고리즘 중 가장 기본이 되는 알고리즘

 

[특징]

1. 대부분의 정렬 알고리즘은 키값을 비교하는 비교 연산과 자료의 위치를 바꾸는 이동 연산으로 이루어짐

2. 비교 연산의 횟수와 이동 연산의 횟수로 정렬의 효율성을 판단

3. 정렬을 수행해야 하는 데이터의 크기가 크면 이동 연산이 적을수록 좋음
(데이터의 크기가 크면 그만큼 이동해야 하는 데이터의 크기가 증가하여 이동 연산을 수행하는데 더 많은 시간이 필요)

4. 연산의 횟수가 같더라도 비교 연산이 많은 알고리즘이 이동 연산이 많은 알고리즘보다 성능이 더 우수

5. 컴퓨터 메모리 내부에서 정렬하는 '내부 정렬 알고리즘'과 보조기억 장치에서 정렬하는 '외부 정렬 알고리즘'이 있음

[시간복잡도]

1. 대부분 O(n^2)과 O(nlogn) 사이
2. 입력이 특수한 성질을 만족하는 경우에는 O(n)정렬도 가능

[종류]

1. 오름차순 정렬이든 내림차순 정렬이든 결과의 형태만 다를 뿐이지 같은 방식으로 처리됨
2. 정렬하는 방법에 대한 정렬 알고리즘은 수십 가지

 

[대표적인 정렬 알고리즘]

1. 선택 정렬 (Selection Sort)
2. 삽입 정렬 (Insertion Sort)
3. 버블 정렬 (Bubble Sort)
4. 셸 정렬 (Shell Sort)
5. 병합 정렬 (Merge Sort)
6. 퀵 정렬 (Quick Sort)
7. 히프 정렬 (Heap Sort)
8. 기수 정렬 (Radix Sort)
9. 계수 정렬 (Counting Sort)

 

[정렬의 종류: 대단위]

종류	설명
내부 정렬 (Internal Sort)	정렬하기 전 모든 데이터가 주기억장치에 로딩되기 때문에 빠르게 정렬할 수 있음. 메모리에 한 번에 로딩하기 어려운 대용량 데이터는 정렬할 수 없음 (ex. 선택, 버블, 삽입, 셸, 병합, 퀵, 히프, 기수 정렬 등)
외부 정렬 (External Sort)	·  데이터의 양이 많아서 디스크와 같은 외부 보조기억장치를 활용하기 때문에 내부 정렬에 비해 수행 속도가 느림 · 내부 정렬이 처리할 수 없는 대용량 데이터를 정렬할 수 있음 ·  주기억장치의 용량만큼씩 보조기억장치의 데이터를 주기억장치로 읽어들여 정렬 ·  입력을 분할해 주기억장치가 수용할 수 있는 만큼의 데이터에 대해 내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여 점진적으로 크기를 늘려나가는 방법