정렬 알고리즘

✳️ 1. 버블 정렬

이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복한다. 

1st 패스

이렇게 입력을 전체적으로 1번 처리하는 것을 패스 (pass) 라고 한다. 1번의 패스가 끝나면, 가장 큰 수 (90) 이 가장 마지막에 위치하며 자리를 확정 짓게 된다. 

시간 복잡도

1,2번 줄의 for 문을 보면 비교횟수는 (n-1) + (n-2) ... {n-(n-1)} = n(n-1) /2  이다.

4번에서 자리 바꿈의 시간은 O(1) 이다. 

=> O(n²) * O (1) = O(n²) 

 

✳️ 2. 선택 정렬

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

시간 복잡도

안쪽 for 문이 한 번에 도는 횟수는 n-1 - (i+1) +1 = n-i+1

바깥 for 문 까지 합하면 도는 횟수는 (n+1) + (n) + (n-1) ... + 3 = n(n-1)/2 

6번에서 자리 바꿈 시간은 O(1)

=> O(n²) * O (1) = O(n²) 

 

특징

- 정렬 정도에 상관없이 항상 일정한 시간 복잡도를 갖는다. 

- 원소 간의 자리바꿈 횟수가 최소인 정렬이다. (패스 당 1번)

 

✳️ 3. 삽입 정렬

배열을 정렬된 부분 (앞부분) 과 정렬 안 된 부분 (뒷부분) 으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입한다. 처음에는 첫 번째 원소만이 정렬되어 있다고 생각하고 시작한다. 

currentElement=50

 

시간 복잡도

* 최악 경우 *

for 문 비교 횟수 n(n-1)/2 

자리 바꿈 시간은 O(1)

=> O(n²) * O (1) = O(n²) 

 

* 최선 경우 : 이미 정렬되어 있음 *

매번 자신의 왼쪽 원소와 비교하기만 하면 된다. 원소의 이동도 없다. 따라서 (n-1) 번의 비교만 하면 된다. 

=>  O(n) 

 

* 평균 경우 *

k번째 요소를 삽입한다고 할 때, 이 요소 앞에는 k-1 개의 정렬된 요소가 있다. 따라서 CurrentElement 는 자신의 자리를 포함하여 총 k개의 자리에 들어갈 수 있다. k 개의 위치 중 들어갈 확률이 모두 같다면, 평균적으로 절반 정도, 즉 k/2번을 비교하고 이동해야 한다. 이 연산은 2번째 요소 부터 n 번째 요소에 대해 반복되기 때문에 Σ(k/2) = n(n-1)/4 이 된다. 

=>  O(n²/4) = O(n²) 

특징

- 거의 정렬된 입력에 대해서 다른 정렬 알고리즘 보다 빠르다. (ex. 앞부분 정렬)

- 입력의 크기가 작을 때 성능이 좋다. 

- 퀵정렬, 합병 정렬에서 입력 크기가 작아지면 순환 호출을 중단하고 삽입 정렬을 사용하는 혼합 방식으로도 사용된다. 

 

✳️ 4. 쉘 정렬

버블 정렬이나 삽입 정렬에서 숫자가 이동할 때는 1칸씩만 이동하기 때문에 시간이 오래 걸린다.

쉘 정렬은 삽입 정렬의 응용으로, 숫자를 '빠르게' 이동시킨다. 

시간 복잡도

쉘 정렬의 시간 복잡도는 사용하는 간격에 따라 다르다. 

 

* 최악 경우 * 

히바드 (Hibbard) 의 간격

2k-1 을 사용하면 

=> O(n^1.5) 

 

* 최선 경우 *

1,4,10...

특징

- 입력 크기가 매우 크지 않을 때 좋은 성능을 보인다. 

✳️ 5. 힙 정렬