Chap 6. 정렬 알고리즘(sort)

[ 정렬이란? ]

정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것이다.

방대한 양의 데이터를 쉽고 빠르게 정보를 찾기 위해 컴퓨터를 사용한다 이를 위한 기본적이고 중요한 알고리즘이 정렬이라고 할수 있다.

 

[ 정렬의 기준 ]

정렬은 여러 가지 기준으로 나눌 수 있다.

(1) “효율적이지만 구현이 어려움 vs 비효율적이지만 구현 쉬움”

 

예를 들어, 퀵 정렬은 효율적이고 빠르지만 구현이 어렵다. 반면, 버블 정렬은 구현이 쉽지만 비효율적인 방법이고 느리다. 

 

(2) “안정성을 보장하는가”

 

안정성은 중복된 key값이 있다면 상대적인 순서가 보장되는 것이다.

예를 들어, 버블 정렬은 같은 "5"라는 숫자도 상대적인 순서를 구분해준다. 즉, 앞에 있는 5와 뒤에 있는 5를 구별한다. 하지만, 삽입정렬은 같은 숫자이기 때문에 둘을 구별하지 않는다.

 

안정적인 정렬  = 버블 정렬, 삽입 정렬, 병합 정렬, 계수 정렬

불안정적인 정렬 = 선택 정렬, 퀵 정렬, 힙 정렬

 

 

(3) “정렬이 어디에서 수행되는지” 등이 있다.

정렬은 외부에서 수행되는 것과 내부에서 수행되는 것으로 나눌 수 있다. 

 

1. 내부 정렬 (internal sort)

레코드를 전부 메인 메모리에 넣고 수행할 수 있는 경우

내부 정렬은 입력 의 크기가 주기억 장치 (main memory)의 공간보다 크지 않은 경우에 수행되는 정렬

버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬, 기수 정렬, 이중 피봇 퀵정렬, Tim sort

 

2. 외부 정렬 (external sort)

입력의 크기가 주기억 장치 공간보다 큰 경우에 보조 기억 장치(하드디스크)에 있는 입력을 한 번에 메인 메모리에 올리기 어렵다.

보조 기억 장치(하드디스크)에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복한다.

 

[ 정렬 알고리즘의 종류 ]

정렬 알고리즘에는 다음과 같은 방법들이 있다. 

앞으로 하나씩 업로드할 계획이다. 

 

6.1 버블 정렬
6.2 선택 정렬
6.3 삽입 정렬
6.4 쉘 정렬
6.5 힙 정렬
6.6 정렬 문제의 하한
6.7 기수 정렬
6.8 외부 정렬