삽입정렬
삽입정렬은 배열을 정렬된 부분과 정렬 안 된 부분으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복하는 방법이다.
그림을 보며 과정을 살펴보면, 우선 정렬된 부분(주황색)과 정렬이 안 된 부분(파란색)으로 나눈 뒤 정렬이 아직 안 된 부분의 가장 왼쪽을 정렬된 부분에 차례로 비교하여 삽입한다.
40 | 60 | 70 | 50 | 10 | 20 | 30 |
1 2 3 4 5 6 7
그림에서 정렬이 안 된 부분 중 가장 왼쪽에 위치한 4번 배열 50을 정렬이 된 부분 오른쪽(배열 3번)부터 차례로 비교한다.
40 | 50 | 60 | 70 | 10 | 20 | 30 |
1 2 3 4 5 6 7
배열 1번까지 비교한 뒤 배열 1보다 크므로 40과 60 사이에 삽입하고 다시 정렬한다.
정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로써, 정렬된 부분의 원소 수가 1개
늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어든다.
이러한 과정을 반복하여 마지막에 정렬이 안 된 부분엔 원소가 남지 않게 되고
정렬 된 부분에 모든 원소가 있게 된다.
삽입정렬 알고리즘
1. for i = 1 to n-1 {
2. CurrentElement = A[i] // 정렬 안된 부분의 가장 왼쪽원소
3. j ←i - 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳을 탐색하기 위하여
4. while (j >= 0) and (A[j] > CurrentElement) {
5. A[j+1] = A[j] // 자리 이동
6. j ←j -1
}
7. A [j+1] ←CurrentElement
}
8. return A
삽입정렬의 알고리즘은 이와 같은 형태로 구성되는데
라인 1번은 삽입 정렬은 정렬이 된 부분에 배열 A[0]만 두고 시작하기 때문에
반복문을 1~(n-1)까지 루프를 준다,
라인 2번은 정렬이 안 된 부분의 가장 왼쪽 원소 A[i]를 CurrentElement라는 변수로 놓는 작업이다.
라인 3번은 j를 정렬 된 부분의 가장 오른쪽 원소의 인덱스로 하고 왼쪽 방향으로 삽입할 곳을 탐색하기 위한 코드이다.
라인 4~6은 CurrentElement가 삽입될 곳을 찾는 과정을 나타낸 알고리즘인데, while문에서 (j >= 0)은 인덱스 j가 배열 범위를 벗어나는 것을 방지하기 위해 사용한 것이고 (A[j] > CurrentElement)는 A[j]를 오른쪽으로 이동시키기 위한 조건이다.
그리고 라인 5번에서 자리이동이 이루어지고 라인 6번은 while문을 반복하기 위한 조건이다.
라인 7은 A[j]의 오른쪽에 CurrentElement를 삽입하기 위함이다.
자세한 수행과정은 그림과 함께 설명한다.
40 | 70 | 60 | 20 | 50 | 10 | 30 |
0 1 2 3 4 5 6
위 그림과 같은 정렬이 되지 않은 배열을 삽입 정렬하는 수행과정을 분석하면
i=1로 두고 CurrentElement는 A[1] 즉 70으로 잡는다.
j = i-1이므로 0이다. A[j] = A[0] < CurremtElement=70 이므로 자리이동 없이 그대로 위치한다.
40 | 70 | 60 | 20 | 50 | 10 | 30 |
0 1 2 3 4 5 6
위 방법을 간단한 식으로 표현하면 i = 2, currentElement A[2] = 60, j=i-1 = 1이고
A[j] = A[1] > CurrentElement = 60이므로 한칸 앞으로 이동한다.
그리고 j=j-1=0 이므로 A[j] = A[0] < CurrentElement = 60, 따라서 CurrentElement를 A[1]에 저장한다.
40 | 60 | 70 | 20 | 50 | 10 | 30 |
0 1 2 3 4 5 6
이러한 방식을 계속해서 반복하여 마지막 i = 6, CurrentElement = A[6] = 30의 결과는 다음과 같다.
10 | 20 | 30 | 40 | 50 | 60 | 70 |
0 1 2 3 4 5 6
이렇게 삽입 정렬이 완료되어 오름차순으로 정렬이 된다.
삽입정렬은 보는 것과 같이 단순한 구도로 구현이 간단하지만 배열이 길어질수록 효율이 떨어진다는 단점이 있다.
끝으로 삽입정렬의 시간복잡도를 살펴보면 삽입 정렬은 위의 알고리즘을 참고하여 라인 1번의 for문이 (n-1)번 수행된다. I = 1일 때 while문이 1번 수행되고 I=2일 때는 최대 2번, 마지막에는 최대 (n-1)번 수행되므로 while문 내부의 라인 5번과 6번이 수행되는 총 횟수는 1 + 2 + 3 + ... + (n-2) + (n-1) =n(n-1)/2이다.
while문 내부의 수행시간은 O(1)이므로 삽입 정렬의 시간복잡도는 O(n^2)가 된다.
쉘 정렬
쉘 정렬은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 쉘의 이름을 따서 붙여졌다. 쉘 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.
쉘 정렬은 버블 정렬이나 삽입 정렬에서 발생하는 시간복잡도 최악의 경우 같은 단점을 보완하기 위해서 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 ‘빠르게’ 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 이동시키고 가장 마지막에는 삽입 정렬을 수행하는 알고리즘이다.
예제를 통하여 자세히 알아보자
[2 5 3 4 3 9 3 2 5 4 1 3]로 리스트가 주어졌을 때 이 리스트를 쉘 정렬을 통해 정렬을 하한다면 다음과 같은 과정으로 수행된다.
우선 간격을 4로 잡고 3행으로 구성된 행렬을 나열하여 열 단위로 정렬한다.
2 5 3 4 2 4 1 2
3 9 3 2 ⇒ 3 5 3 3
5 4 1 3 5 9 3 4
정렬된 3행 행렬을 6행으로 나열하여 마찬가지로 열 단위로 정렬한다.
2 1 2 1
3 3 3 2
5 3 ⇒ 4 3
4 2 5 3
5 3 5 3
9 4 9 4
정렬된 행렬을 한 열로 나열해서 삽입 정렬한다.
2 3 4 5 5 9 1 2 3 3 3 4 ⇒ 1 2 2 3 3 3 3 4 4 5 5 9
예제와 같이 쉘 정렬을 수행할 땐 첫 간격을 정하는 것이 중요하다.
간격을 점차 줄여가며 그룹을 나누어 그룹별로 정렬하는 과정을 계속 수행하여 마지막엔 반드시 간격을 1로 놓고 수행하도록 한다.
그 이유는 다른 그룹에 속해 서로 비교가 되지 않은 숫자가 있을 수 있기 때문이다.
다시 말하면 본 예시의 마지막처럼 한 열로 나열하여 각 원소를 1개 그룹으로 본 다음 삽입정렬을 수행하는 방법이다.
쉘 정렬의 알고리즘을 보면 다음과 같다.
1. for each gap h = [ h0 > h1 > ... > hk=1] // 큰 gap부터 차례로
2. for i = h to n-1 {
3. CurrentElement=A[i];
4. j = i
5. while (j>=h) and (A[j-h]>CurrentElement) {
6. A[j]=A[j-h];
7. j=j-h;
}
8. A[j]=CurrentElement;
}
9. return 배열 A
라인 1번의 [ h0 > h1 > ... > hk=1]처럼 쉘 정렬의 간격은 미리 정해야 한다.
그 후 간격이 가장 큰 h0부터 차례로 라인 2~8번처럼 삽입 정렬이 수행된다.
마지막 간격인 hk는 반드시 1이여야 하는데 이는 앞서 말한 서로 그룹이 달라 비교되지 않은 숫자가 있을 경우를 위함이다.
라인 2~8번의 for문은 보는 것과 같이 간격 h에 대해 삽입 정렬이 수행되는데
라인 2번 for문의 조건에선 I를 h부터 1씩 증가시켜 currentElement A[i]를 각 그룹별 원소끼리 비교하도록 한다.
라인 5~7번 while문에선 courrentElement를 앞부분부터 삽입 하는데 첫 번째 조건인 (j>=h)는 배열의 범위를 벗어나는지 확인 하기 위함이고 2번째 조건인 (A[j-h]>CurrentElement) 는 (j-h)가 음수가 아니면 currentElement를 자신의 그룹 원소인 A[j-h]와 비교하여 크면 라인 6번의 (A[j]=A[j-h]) 즉 A[j-h]를 h만큼 뒤로 이동시킨다.
while문의 조건이 거짓이 되면 라인 8번에서 A[j] = currentElement를 수행하여
currentElement를 A[j]에 저장한다.
쉘 정렬의 수행속도는 간격 선정에 좌우된다.
지금까지 알려진 가장 좋은 성능을 보인 간격은 [1, 4, 10, 23, 57, 132, 301, 701]인데
701 이후는 아직 밝혀지지 않았다.
시간복잡도를 보면서 이에 대해 더 자세히 이야기 해보면 쉘 정렬의 최악 경우의 시간복잡도는 O(n2)이다.
히바드(Hibbard)의 간격 2k-1 (즉, 2k-1, ⋯, 15, 7, 5, 3, 1)을 사용하면 시간복잡도는 O(n1.5)이다.
많은 실험을 통한 쉘 정렬의 시간복잡도는 O(n1.25)으로 알려지고 있다.
사실 쉘 정렬의 시간복잡도는 아직 풀리지 않은 문제인데 그 이유는 가장 좋은 간격을 알아내는 것이 우선 되어야 하기 때문이다.
쉘 정렬은 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보인다.
주로 임베디드 시스템에서 사용되는데 이는 쉘 정렬의 특징인 간격에 따른 그룹별 정렬 방식이 하드웨어로 정렬 알고리즘을 구현하는 데 매우 적합하기 때문이다.
'자료구조,알고리즘' 카테고리의 다른 글
| (알고리즘)m-coloring 문제해결 (0) | 2019.02.11 |
|---|---|
| (자료구조)원형 큐 (0) | 2019.02.11 |
| 선택정렬 (0) | 2019.02.10 |
| 퀵 정렬 코드 및 실행결과 (0) | 2019.02.10 |
| 퀵 정렬 (0) | 2019.02.10 |