[문제 해결 알고리즘] 정렬 알고리즘 ①

1. 버블 정렬

(1) 정의

- 실제로 많이 사용하지는 않음

- 다른 정렬에 비해 시간복잡도가 높고 연산 처리 속도나 나쁨

- 정렬 알고리즘의 분류 :

기본적인 정렬 알고리즘 = 버블 정렬, 선택 정렬, 삽입 정렬

효율적인 정렬 알고리즘 = 쉘 정렬, 힙 정렬, 합병 정렬, 퀵 정렬, 기수 정렬(입력이 제한된 크기 이내에 숫자로 구성되어 있을 때 효율적)

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

- 외부 정렬 : 입력의 크기가 주 기억장치 공간보다 큰 경우, 보조 기억 장치에 있는 입력을 여러번에 나누어, 주 기억 장치에 읽어들인 후 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복해야 할 때 수행되는 정렬

- 버블 정렬 :  이웃하는 숫자를 비교하여 작은 수를 앞쪽(또는 큰 수를 뒤쪽)으로 이동시키는 과정을 반복하여 정렬하는 알고리즘

- 오름차순으로 정렬한다면 작은 수는 배열의 앞 부분으로 이동하는데, 배열을 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품으로 위로 올라가는 것을 연상케함

- 패스 : 입력을 전체적으로 1번 처리하는 것

(2) 알고리즘

- 입력 : 크기가 n인 배열 A

- 출력 : 정리된 배열 A

ⓐ for pass = 1 to n-1

ⓑ for i =1 to n-pass

ⓒ if(A[i-1] > A[i])

ⓓ A[i-1] ↔ A[i]

ⓔ return 배열 A

(3) 시간 복잡도 = O(n(n-1)/2) = O(n^2)

2. 선택 정렬

(1) 정의

- 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 배열의 1번 원소와 자리를 바꿈

- 마지막에 2개 원소 중 최솟값을 선택하여 자리를 바꿈으로써 오름차순 정렬의 마무리

(2) 알고리즘

- 입력 : 크키가 n인 배열 A

- 출력 : 정리된 배열 A

ⓐ for i = 0 to n-2 {

ⓑ min = i

ⓒ for j=i+1 to n-1 {

ⓓ if(A[j] < A[min]) : min = j

ⓔ A[i] ↔ A[min] }}

ⓕ return 배열 A

(3) 시간 복잡도 = O(n(n-1)/2) = O(n^2)

(4) 특징

- 입력에 민감하지 않은 알고리즘

- 거의 정렬되어 있는지 구분하지 않음

- 역으로 정렬되어 있는지 구분하지 않음

- 랜덤하게 되어있는지 구분하지 않음

- 항상 일정한 시간 복잡도를 나타냄

3. 삽입 정렬

(1) 정의

- 배열을 정렬된 부분(앞부분)과 정렬 안된 부분(뒷부분)으로 나누고 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복함

(2) 알고리즘

- 입력 : 크기가 n인 배열 A

- 출력 : 정리된 배열 A

ⓐ for i = 1 to n-1

ⓑ CurrentElement = A[i]

ⓒ j = i-1

ⓓ while (j>=0 and A[j] > CurrentElement) {

ⓔ A[j+1] = A[j] }

ⓕ A[j+1] = CurrentElement }

ⓖ return A

(3) 시간 복잡도 = 최악의 경우 O(n^2)

(4) 특징

- 입력의 상태에 따라 수행 시간이 달라짐

- 입력이 이미 정렬되어 있으면 각각 Current Element가 자신의 왼쪽 원소봐 비교 후 자리 이동 없이 원래 자기 자리에 있게되고 while 루프의 조건이 항상 거짓이므로 원소의 이동도 없음

- n-1 비교만 진행하면 됨

- 최선의 경우 시간 복잡도 = O(n), 삽입 정렬은 거의 정렬된 입력에 대해서 다른 정렬 알고리즘보다 빠르다

- 최악의 경우 시간 복잡도 = O(n^2), 역으로 정렬된 입력에 대해서는 O(n^2)의 시간이 걸림