정렬 알고리즘

 정렬 알고리즘은 말그대로 정렬하는 알고리즘이다.

1. 분류

1) 내부정렬

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

2) 외부정렬

 입력의 크기가 주기억 장치의 공간보다 커, 보조 기억 장치에 있는 입력을 여러 번 나누어 주기억 장치에 읽어들인 후, 보조 기억 장치에 다시 저장하는 과정을 반복하는 정렬

2. 알고리즘

1) 버블 정렬

 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬, 즉 마지막 값이 가장 큰 값이 되도록 만드는 것

2) 선택 정렬

 입력 배열 전체의 최솟값을 선택하여 배열의 0번의 값과 바꾸고 0번을 제외한 나머지 원소에서 위의 과정을 반복하는 방법

3) 삽입 정렬

 정렬이 된 부분과 안된 부분으로 나누고 정렬이 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 원소들을 순차적으로 비교하여 적절한 위치에 삽입하는 방법

(단, 대부분 정렬이 잘 되어 있는 것일때 효율적이고 역 정렬이 되어있을 때에는 비 효율적이다)

4) 쉘 정렬

 다른 정렬이 하나씩 순차적으로 이동하는 것을 보완하기 위하여, 입력 배열 전체를 일정한 간격으로 나누고 각 자리마다 원소를 비교한 다음, 더 작은 간격으로 나누고 위의 과정을 반복하는 방법

5) 힙 정렬

 힙 조건을 만족하는 완전 이진트리이며, 힙 조건이란 각 노드의 값이 자식노드의 값보다 크거나 작은 것을 말한다.