2015년 9월 3일 목요일

정렬 알고리즘(Sort Algorithm) (5) - 셸 정렬(Shell Sort)

1. 셸 정렬(Shell Sort)?
셸 정렬은 삽입 정렬의 단점인 원소를 적합한 위치에 삽입하기 위해 원소들을 뒤로 옮기는 과정을 줄이기 위해, 특정한 거리씩 떨어진 원소들끼리 삽입정렬을 하고, 그 거리을 차츰 줄여나가면서, 최종적으로는 전체 원소들에 대해 삽입정렬을 하는 알고리즘입니다.
※ 삽입 정렬에 대한 내용은 정렬 알고리즘(Sort Algorithm) (4) - 삽입 정렬(Insertion Sort)(http://juffalgorithm.blogspot.kr/2015/09/sort-algorithm-4-insertion-sort.html)를 참조해주세요.

2. 예시

5
1
9
3
7
8

데이터를 가지고 직접 셸 정렬을 해봅시다. (여기서는 원소간 거리가 3, 1로 줄어드는 경우로 합니다.)

1. 거리가 3만큼 떨어진 원소끼리 삽입 정렬을 한다.
5
1
9
3
7
8
삽입할 원소 : 3
5
1
9
5
7
8
삽입할 원소 : 3
3
1
9
5
7
8
삽입할 원소 :


3
1
9
5
7
8
삽입할 원소 : 7
3
1
9
5
7
8
삽입할 원소 :

3
1
9
5
7
8
삽입할 원소 : 8
3
1
8
5
7
9
삽입할 원소 : 8
3
1
8
5
7
9
삽입할 원소 :

2. 거리가 1만큼 떨어진 원소끼리 삽입 정렬을 한다.
3
1
8
5
7
9
삽입할 원소 : 1
3
3
8
5
7
9
삽입할 원소 : 1
1
3
8
5
7
9
삽입할 원소 :
1
3
8
5
7
9
삽입할 원소 : 8
1
3
8
5
7
9
삽입할 원소 :
1
3
8
5
7
9
삽입할 원소 : 5
1
3
8
8
7
9
삽입할 원소 : 5
1
3
5
8
7
9
삽입할 원소 :
1
3
5
8
7
9
삽입할 원소 : 7
1
3
5
8
8
9
삽입할 원소 : 7
1
3
5
7
8
9
삽입할 원소 :
1
3
5
7
8
9
삽입할 원소 : 9
1
3
5
7
8
9
삽입할 원소 :

1
3
5
7
8
9

3. 특징

셸정렬은 인접한 원소간의 정렬이 아닌 떨어진 원소간의 정렬로 인해 같은 우선순위를 갖는 원소간의 순서가 보존되지 않는다.



4. C를 이용한 구현

다음 코드는 원소간 거리를 데이터의 절반에서 부터 시작하여, 정렬이 완료될 때까지 반으로 나눠가는 방법을 사용하였다.


4. 원소간 거리를 어떻게 정해야 하는가?
셸 정렬의 기본전략은 삽입정렬 과정에서 원소를 뒤로 옮기는 횟수를 줄이는 것으로 속도를 향상시키는데 있다. 하지만, 삽입정렬 횟수가 너무 많거나, 적게 된다면, 이러한 효과가 떨어진다. 때문에 원소간 거리에 대한 최적화된 수열을 사용한다면 속도를 더욱 향상시킬 수 있게된다.
작성자: 시간: 댓글 없음:
라벨: , , , ,

정렬 알고리즘(Sort Algorithm) (4) - 삽입 정렬(Insertion Sort)

1. 삽입 정렬(Insertion Sort)?
삽입 정렬은 원소들을 정렬된 영역에서 원소가 들어갈 위치를 찾아서 삽입하는 과정을 반복하여 정렬을 행하는 알고리즘입니다.

2. 예시
5
1
3
8
7

데이터를 가지고 직접 삽입 정렬을 해봅시다.

1. 삽입할 원소를 기억해둔다.
5
1
3
8
7
삽입할 원소 : 1
2. 정렬된 구간(삽입된 원소의 앞쪽 구간)에서 원소가 삽입될 위치를 찾으면서, 삽입될 공간을 확보하기 위해 원소들을 뒤로 옮겨준다.
5
5
3
8
7
삽입할 원소 : 1

3. 삽입될 위치를 찾았으면, 기억해둔 원소를 넣는다.
1
5
3
8
7
삽입할 원소 :

4. 1~3을 반복한다. 
1
5
3
8
7
삽입할 원소 : 3
1
5
5
8
7
삽입할 원소 : 3
1
5
5
8
7
삽입할 원소 : 3
1
3
5
8
7
삽입할 원소 :
1
3
5
8
7
삽입할 원소 : 8
1
3
5
8
7
삽입할 원소 : 8
1
3
5
8
7
삽입할 원소 :
1
3
5
8
7
삽입할 원소 : 7
1
3
5
8
8
삽입할 원소 : 7
1
3
5
8
8
삽입할 원소 : 7
1
3
5
7
8
삽입할 원소 :

1
3
5
7
8

3. 특징
 삽입정렬은 원소를 정렬된 영역에 추가로 삽입하는 동작을 반복하기 때문에, 이미 정렬된 배열은 매우 짧은 시간에 정렬작업이 완료된다. 또한, 정렬된 배열에 이미 원소가 추가되는 형태의 경우, 추가된 원소에 대해서만 정렬을 수행하게 되는 특징이 있다. 하지만, 반대로 정렬된 배열의 경우 모든 원소들에 대해 비교 연산을 수행하게 되어 최악수행시간이 된다. 최악의 경우 이미 정렬된 배열에 대해 비교연산을 전부 수행하므로 1+2+3+...+N이 되어 O(N^2)이 된다.
 
4. C를 이용한 구현


 삽입될 원소가 이미 정렬된 원소들보다 작은 경우 배열의 밖을 참조하려고 하는 일이 발생할 수 있으므로, 예외처리가 필요하다. 이를 하지 않고 맨앞에 매우 작은 값으로 '보초'를 넣는 기법도 생각해 볼 수 있으나, 상황에 따라 이것이 불가능 할 수 있으므로, 주의가 필요하다.
작성자: 시간: 댓글 없음:
라벨: , , , ,

2015년 8월 28일 금요일

정렬 알고리즘(Sort Algorithm) (3) - 합병 정렬(Merge Sort)

1. 합병 정렬(Merge Sort)?
합병 정렬은 작은 구간들을 정렬된 상태로 합병해나가면서, 구간의 크기를 키워가면서 정렬하는 알고리즘입니다.

1.1 어떻게 두 구간을 합병하는가?
두 구간은 각각 이미 정렬된 상태이기 때문에 두 구간을 합병할 때 두 구간은 일종의 스택(Stack)으로써 맨 앞에는 각 구간의 최소값을 갖는 원소가 들어있게 된다. 이 최소값을 비교하여 둘 중 작은 값을 꺼내주기(pop)를 반복하면, 두 구간의 원소들이 정렬된 상태로 합병되게 한다.

두 구간의 합병 과정을 예를 통해 표현하면 다음과 같다.




2. 예시
3
8
7
1
5

데이터를 가지고 직접 합병 정렬을 해봅시다.

1. 구간을 설정한다.

3
8
7
1
5
2. 구간끼리의 합병을 한다.
3
8
7
1
5
3
8
1
7
5
3
8
1
7
5
3. 1~2를 반복한다. 
1
3
7
8
5
1
3
5
7
8
1
3
5
7
8
3. C를 이용한 구현


 위 의 코드의 경우, 매번 합병할 때마다 구간내 원소를 복사해서 합병을 하기 때문에 속도가 느려진다. 하지만, 포인터로 합병할 원소들이 있는 주소와 합병된 원소들이 있는 주소를 조작해주면 복사하는 과정이 없어지기 때문에 속도가 향상된다. 다만, 이 때 결과값이 최종적으로 원래의 배열에 들어가도록 주의하여야한다.
다음은 포인터를 이용하여 합병시마다 반복되는 복사과정을 없앤 합병 정렬이다.
작성자: 시간: 댓글 없음:
라벨: , , , ,

2015년 8월 27일 목요일

정렬 알고리즘(Sort Algorithm) (2) - 거품 정렬(Bubble Sort)

1. 거품 정렬(Bubble Sort)?
거품 정렬은 인접한 원소들끼리 비교하여 큰 것을 뒤로 보내서 점차적으로 정렬하는 알고리즘입니다.

2. 예시
5
8
7
1
3

데이터를 가지고 직접 거품 정렬을 해봅시다.

1. 가장 큰 수를 뒤로 보내기 위해 인접한 수끼리 비교를 행하여 교환해준다.
5
8
7
1
3
5
8
7
1
3
5
7
8
1
3
5
7
8
1
3
5
7
1
8
3
5
7
1
8
3
5
7
1
3
8
2. 맨 뒤의 숫자를 제외하고 1을 반복한다.
5
7
1
3
8
5
7
1
3
8
5
1
7
3
8
5
1
7
3
8
5
1
3
7
8

5
1
3
7
8
1
5
3
7
8
1
5
3
7
8
1
3
5
7
8
1
3
5
7
8


4. 특징

거품 정렬은 인접한 원소끼리 교환하는 특성 때문에 정렬과정에서 원소들의 순서가 보존된다. (Stable)
거품 정렬은 별도의 데이터를 저장하기 위한 배열이 필요하지 않다. (Inplace)
5. C를 이용한 구현



6. 사다리 타기
거품 정렬은 인접한 원소끼리 교환하는 특성 때문에, 사다리 타기의 결과가 주어질경우 원소의 교환이 발생하는 것을 기억해놓을 경우 그 결과가 나오는 사다리를 만들어 낼 수 있습니다.
작성자: 시간: 댓글 없음:
라벨: , , , ,

정렬 알고리즘(Sort Algorithm) (1) - 선택 정렬(Selection Sort)

1. 선택 정렬(Selection Sort)?
선택 정렬은 가장 작은 것을 찾아서 맨 앞에 놓고, 그 다음 작은 것을 찾아서 그 다음에 놓고 식으로 정렬을 행하는 알고리즘입니다.

2. 예시
5
8
7
1
3

데이터를 가지고 직접 선택 정렬을 해봅시다.

1. 가장 작은 숫자를 찾는다.
5
8
7
1
3

2. 찾은 숫자를 맨 앞으로 위치 시킨다. (원래 맨 앞에 있던 숫자와 위치를 바꾼다.)
1
8
7
5
3

3. 맨 앞의 숫자를 제외하고 1~2를 반복한다.
1
8
7
5
3
1
3
7
5
8
1
3
7
5
8
1
3
5
7
8
1
3
5
7
8
1
3
5
7
8
1
3
5
7
8

3. 특징
 선택 정렬은 가장 작은 것을 찾아서 앞에 배치하는 것을 반복하는 알고리즘이므로, 별도의 데이터를 저장하기 위한 배열이 필요하지 않다. (Inplace)
 선택 정렬은 정렬과정에서 원소들의 순서가 보존되지 않는다. (Stable하지 않음)
 예를 들어, 57713을 정렬할 경우, 두 7의 순서가 보존되지 않는다.

4.시간복잡도
 선택 정렬은 가장 작은 숫자를 찾고, 그 숫자를 가장 앞에 위치하도록 하는 것을 반복하는 알고리즘이다.
 이 알고리즘의 시간복잡도를 분석하면 다음과 같다. (데이터의 개수는 N)
제일 작은 숫자를 찾기 위해 1~N번째 데이터들을 체크 -> N개의 원소
 2번째로 작은 숫자를 찾기 위해 2~N번째 데이터들을 체크 -> N-1개의 원소
 3번째로 작은 숫자를 찾기 위해 3~N번째 데이터들을 체크 -> N-2개의 원소
 ....
 N-1번째로 작은 숫자를 찾기 위해 N-1~N번째 데이터들을 체크 -> 2개의 원소
 순서를 바꾸는데 걸리는 시간은 O(1), 각각의 데이터들을 체크하는데 걸리는 시간은 O(1)이므로, 총 시간복잡도는 O(1+2+3+...+N-1)이 되어 O(N^2)이 된다.

5. C를 이용한 구현
C를 이용해 구현한 선택정렬 알고리즘 소스코드
작성자: 시간: 댓글 없음:
라벨: , , , ,
피드 구독하기: 글 (Atom)