효율적인 정렬 알고리즘 (쉘 정렬, 병합 정렬, 퀵 정렬)

728x90

반응형

SMALL

효율적인 정렬 알고리즘 

쉘 정렬	주어진 입력 데이터를 적당한 매개 변수의 값만큼 서로 떨어진 데이터들과 비교하여 교환하는 과정을 매개 변수의 값을 바꾸어가며 되풀이하는 것이다.
병합 정렬	정렬할 데이터들을 2개로 나누고 2개로 나뉜 데이터들을 각각 정렬한 다음에 다시 합병하여 하나의 정렬된 데이터들로 완성하는 방법이다.
퀵 정렬	기준 키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.

---

01. 쉘 정렬

1. 쉘 정렬 (Shell Sort)

주어진 입력 데이터를 적당한 매개 변수의 값만큼 서로 떨어진 데이터들과 비교하여 교환하는 과정을 매개 변수의 값을 바꾸어가며 되풀이하는 것

전체 데이터가 있으면 바로 옆에 있는 데이터를 비교하는 게 아니라 매개 변수를 5 정도로 준다면 현재 위치에서 5자리만큼 떨어져 있는 데이터들끼리 비교해서 정렬하고, 그 옆에 있는 데이터도 마찬가지로 5자리만큼 떨어져 있는 데이터들끼리 비교해서 정렬한다. 

 

매개 변수를 처음에는 5로 줬다가, 그 다음에 3으로 줬다가, 2로 줬다가, 1로 줬다가

이런식으로 매개변수값을 줄여간다던지 이런 식으로 해서 정렬하는 방법을 쉘 정렬이라고 한다. 

 

영역을 나눈 후 삽입하는 보완된 삽입 정렬 개념

삽입정렬이라는 게 데이터가 어느 정도 정렬이 되었을 때 굉장히 빠른 알고리즘인데, 쉘 정렬로 매개 변수를 바꿔가면서 정렬하다 보면 데이터들이 대략적으로 어느 정도 정렬이 되어간다. 그래서 최종적으로는 가장 마지막에 삽입 정렬을 한다. (매개 변수가 1일 때) 그렇기에 보완된 삽입 정렬이다.라고 이야기하기도 한다. 

 

입력 파일을 어떤 매개변수의 값으로 서브파일을 구성하고,

각 서브파일을 삽입 정렬 방식으로 배열하는 과정을 반복하는 정렬 방식

 

이때 서로 떨어져 있는 데이터들은

하나의 부분 리스트를 구성하게 되며 마지막으로 삽입 정렬에 의해 개별적으로 정렬 됨

 

먼저 적절한 매개 변수의 값을 선택한 후 점차 감소시켜 가면서 쉘 정렬을 수행하고 매개 변수의 값이 1이 될 때 종료함

그래서 삽입 정렬도 쉘 정렬을 통해서 하게도 되는데 삽입 정렬 자체가 거의 정렬된 입력에 대해서 다른 정렬 알고리즘 보다 빠르다.

---

2. 쉘 정렬의 작동 예

예) 다음의 데이터를 쉘 정렬로 정렬하시오.

---

풀이)

1. 먼저 간격(Gap)이 5가 되는 숫자끼리 그룹을 만든다.

총 15개의 숫자가 있으므로 첫 번째 그룹은 첫 숫자인 30, 첫 숫자에서 간격이 5되는 숫자인 80, 그리고 80에서 간격이 5인 50으로 구성된다.  

● 첫 번째 그룹은 [30, 80, 50]이다. ● 두 번째 그룹은 [60, 40, 30]이고, 나머지 그룹은 각각 [90, 20, 40], [10, 10, 90], [40, 60, 80]이다.

 

---

2. 그룹별로 삽입 정렬을 수행한다.

매개 변수가 5일 때, h = 5

1차적으로 매개 변수를 5로 해서 봤더니 (간격이 5인 그룹 별로 정렬) 

80과 90 같은 큰 숫자가 뒷부분으로 이동하였고, 20과 30 같은 적은 숫자가 앞부분으로 이동한 것을 알 수 있다.

이런 식으로 대략 정리가 된다.

---

3. 그다음엔 간격을 5보다 작게 한다.

예를 들어 3으로 하여 3개의 그룹으로 나누어 각 그룹별로 삽입 정렬을 수행하는데 이때에는 각 그룹에 5개의 숫자가 있다.

1차적으로 Gap을 5로 놔눴을 때 [30 30 20 10 40 50 40 40 10 60 80 60 90 90 80]으로 정렬이 되었는데, 이것을 이제 h = 3으로 한다라면 첫 번째 그룹은 첫 시작인 30, 첫 숫자에서 간격이 3되는 숫자 10, 그리고 10에서 간격이 3인 40, 40에서 간격이 3인 60, 60에서 간격이 3인 90이 하나의 서브파일이 된다. 이 5개의 데이터들 사이에 삽입 정렬이 일어나는 것이다. 

그래서 첫 번째 그룹을 삽입 정렬하면 [30 10 40 60 90] → [10 30 40 60 90]이 된다. 

 

마지막에는 반드시 간격을 1로 놓고 수행해야 하는데 다른 그룹에 속해 서로 비교되지 않은 숫자가 있을 수 있기 때문이다.

매개 변수를 1로 놓는다.라는 것은 현재 위치를 기준으로 하나만큼 떨어진 간격이니깐 각각 이웃하는 항들에 대한 것이기 때문에 결국에는 이 전체의 데이터를 한 개의 그룹으로 나누는 것이다. 

즉, 모든 원소를 1개의 그룹으로 여기는 것이고 이는 삽입 정렬이다.  

 

쉘 정렬은 매개 변수가 큰 특징이다.

매개 변수를 기준으로 일정한 간격만큼 떨어진 데이터들끼리 정렬을 하는 것인데, 그 정렬이 또 삽입정렬이 일어나기 때문에 쉘 정렬은 개선된 삽입정렬이다. 보안된 삽입정렬이다. 라고 말을 한다.

---

3. 쉘 정렬 복잡도

쉘 정렬은 최악 경우(Worst Case)의 시간복잡도

쉘 정렬의 수행 속도는 간격 선정에 따라 좌우된다. 

 

좋은 간격

수행 시간을 가장 적당하게, 가장 적게 하는 간격을 선택해야 된다.

---

4. 쉘 정렬의 특징

쉘 정렬은 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보인다.

쉘 정렬은 임베디드 시스템에서 주로 사용되는데 쉘 정렬의 특징인 간격에 따른 그룹 별 정렬 방식이 하드웨어로 정렬 알고리즘을 구현하는데 매우 적합하기 때문이다. 

 

임베디드 시스템은 기존의 가전제품에다가 약간의 컴퓨터적인 프로그램을 추가하기 위해서 삽입된 

말 그대로 embeded (내장된) 된 것이다. 삽입되고, 포함된, 이런 시스템이기 때문에 임베디드 시스템 안에 들어가는 데이터라던지 이런 것들은 사실 규모가 크지 않다. 그래서 이런 임베디드 시스템에 주로 쉘 정렬이 사용된다.

 

쉘 정렬의 특징 간격 

5로 놓느냐, 3으로 놓느냐, 2로 놓느냐, 1로 놓느냐 간격에 따라서 그만큼 떨어진 데이터들끼리 정렬을 하는 것이다. 즉, 간격에 따라서 그룹별로 정렬하는 방식이 하드웨어로 정렬 알고리즘을 구현하는데 매우 적합하기 때문에 이런 쉘 정렬 알고리즘은 임베디드 시스템에서 굉장히 많이 쓰이는 정렬 알고리즘 중에 하나이다. 

 

# 임베디드 시스템 

가전제품이나, 어떤 전자 제품에 일부 컴퓨터 칩이 있는데, 그 칩 안에 일부 프로그램을 내장하는 것이다.

---

02. 병합 정렬

1. 병합 정렬 (Merge Sort)

정렬할 데이터들을 2개로 나누고 2개로 나뉜 데이터들을 각각 정렬한 다음에 다시 합병하여 하나의 정렬된 데이터들로 완성하는 방법

이미 정렬되어 있는 두 개의 파일을 1개의 파일로 합병하는 정렬 방식으로 1개의 파일에서는 각각의 데이터를 하나의 파일로 취급하여 정렬한다. 

 

# Merge

2개 이상의 것을 합한다는 뜻이다. 

 

병합 정렬은 점화식으로도 많이 표현을 했다. 

점화식이라는 게 크기만 다를 뿐이지 자기하고 비슷한 동작을 계속 반복하는 것이다.

병합 정렬도 마찬가지로 전체 데이터를 반으로 나누고 그 각각을 정렬해서 최종적으로 이 둘을 정렬해서 합하는 것이다.라고 설명이 되어있지만 내부 알고리즘을 보면 사실 여러 단계가 추가가 된다.

 

어떤 여러 단계가 추가가 되느냐?

원래 데이터가 있는데 이것을 반으로 나눈다고 했다. 2분의 1, 2분의 1로 나눈다. 이 각각이 자체적으로 정렬되는 게 아니라

사실 나뉜 2분의 1이 또 2분의 1로 나뉜다. 그러면 4분의 1이 나온다. 계속 이런 식으로 나뉘고 가장 마지막에는 원소가 하나씩 나온다. 이런식으로 되어서 마지막 원소, 마지막 원소를 정렬해서 병합하고 또 그위를 올라가 정렬해서 병합하고 

또 위로 올라가 나뉜 것들을 정렬해서 병합하여 하나로 만들고 또 위로 올라가 최종적인 원래의 하나의 데이터의 정렬값을 얻어가는 과정을 반복한다. 그래서 보면 원래 n개였는데, 2분의 n개로 줄었고, 또 4분의 n개 계속 이런 식으로 줄어든다. 

즉, 현재 사이즈에서 절반씩 줄어들지만 이 동작 자체는 비슷하다. 그래서 이런 것들을 점화식으로 표현을 한다.

---

 

점화식 할 때 T(n)일떄 T에 2분의 n인 것이 2개에다가 플러스 오버헤드라고 해서 각각을 병합하는 그 시간

대개 n logn 정도의 시간을 갖는다.라고 했는데, 이런 오버헤드가 더해진 그런 정도의 복잡도를 갖는다.

 

병합 정렬이 점화식으로도 활용할 수 있고

또 재귀함수, 점화식으로 표현할 수 있는 건 재귀 호출(Recursive Call) 자기 자신을 호출하는 그런 알고리즘 

그런 형태로도 구현할 수 있다. 

 

임의의 함수가 자신을 호출하는 것을 재귀 호출이라 하고,

재귀 호출을 이용하는 알고리즘을 재귀 알고리즘이라고 한다.

---

1. 병합 정렬 알고리즘

A라는 배열에 정렬하고자 하는 전체 데이터가 있다.

배열의 인덱스 p부터 r까지 데이터가 있다. 이 데이터를 정렬을 하는 게 최종 목적이다.

 

병합 정렬을 할 때

	p하고 r을 비교해서 밑의 과정을 수행한다. p가 r보다 커지면 IF문장에서 빠져나온다.
	① p가 r보다 작다면 p와 r을 더해서 2로 나누어라      이것은 p와 r을 반으로 나눌려고 중간값을 계산하는것이다. 중간값은 q이다.      그러면 p와 q까지 하나의 그룹이 되고, q+1과 r까지가 하나의 그룹이 된다.  그러면 1번에 해당하는 그룹 정렬하고, 뒷부분에 해당되는 q+1과 r까지를 정렬해서 애를 최종적으로 merge 하나로 합하는 그런 동작이 된다.
	② mergeSort(A, p, q) mergeSort를 봤더니 자기 자신이다. 지금 자기 자신의 함수를 호출하는 것이다. 재귀 호출을 하는것이다.  A의 p에서 q 까지  이것을 또 mergeSort를 한다. mergeSort를 수행하는 과정을 보면 다시 위로 올라가서 수행을 하기 때문에 p, q를 또 반으로 나눈다. 그럼 p, q는 절반이 된다.
	③ mergeSort(A, q+1, r) 위 2번과 같이 또 q+1부터 r을 반으로 나눈다.
	④ mergeSort(A, p, q, r) 최종적으로 계속 2개, 2개, 2개 나뉘어져가지고 각각을 정렬한것을 병합하고 병합하고 병합했을 때 이 병합하는 과정의 mergeSort부분이다. 그래서 최종적으로는 계속해서 병합이 쭉 되가면서  각각의 값이 비교되어 뭐가 먼저 와야되는지 이런것들이 순서대로 정렬을 할 수 있다.  ① ~ ④은 대략적인 알고리즘이다.  상세적으로 알고리즘을 더 짜면 merge하는 방법으로 세부적인 동작이 들어간다.

---

2. 병합 정렬의 작동 예

 

---

과정 

p에서 q까지 하나의 그룹 q+1에서 r까지 하나의 그룹

3을 i라고 놓고, 11을 j라고 놓을 수 있다. t는 새로운 배열이다.

이 두 개의 배열을 하나로 병합하고자 할 때의 인덱스를 t라고 둘 수 있다. 

 

각 그룹의 첫 번째 3과 11을 비교한다.  

3과 11을 비교해서 3이 더 작으니깐 t의 첫 번째에 둔다.

그러면 t배열에 3 하나가 증가되고 p부터 q까지 그룹에서 3은 제외된다.

 

i값이 하나 증가되어서 8과 11을 비교한다.

8이 더 작으므로 3 뒤에 8이 온다. 

 

31과 11을 비교한다. 

i가 증가되면 앞쪽은 고려하지 않는다. 이미 병합이 되었기 때문이다.

11이 더 작으므로 t의 배열에 11 값이 들어오게 된다. 

 

11이 병합이 되었기 때문에 고려대상에서 빠지고 j를 하나 증가시켜 i에 해당되는 31과 j에 해당되는 15를 비교한다. 

15가 작으니깐 t배열에 11 다음으로 들어오게 된다. 

 

j를 하나 증가시켜 20과 i 31을 비교한다.

20이 작으니깐 t의 배열에 들어간다.

 

이런 과정을 거쳤더니

데이터들이 정렬이 되었다. 

이 마지막 부분은 각각 정렬된 두 개의 그룹을 하나의 배열로, 하나로 merge 한, 병합한 것이다.

---

3. 병합 정렬의 수행 시간 

왜 o에 n 로그앤이 되었는지 아는가?

병합정렬을 보면 이진트리의 형태이다. 하나의 데이터가 반으로 나눠지고 반으로 나눠진 데이터가 또 밑에 하위에 자식 노드가 달리는 그런 트리의 형태가 되기 때문이다. 즉 자식이 둘 달린 트리 형태 이진 트리가 된다. 그래서 이것에 대한 실제 수행 시간이라는 것은 트리의 높이인데, 높이에 해당되는 부분은 n logn이다. 그런 부분에 대한 수행시간이라고 생각할 수가 있어서 O에 n logn 만큼의 수행 시간, 복잡도를 갖는다.라고 할 수가 있는 것이다.

---

03. 퀵 정렬

1. 퀵 정렬 (Quick Sort)

퀵 정렬

빠른 정렬이다.라고 이야기할 수도 있다. 이것은 기준 키가 필요하다. 

 

기준 키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해 가며 정렬하는 방법

평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘 

 

# 가장 좋은 성능

검색 속도가 빠르다는 의미로도 해석할 수 있다.

---

2. 퀵 정렬의 작동 예

	① 맨 앞의 20을 기준키로 하고 기준키 다음부터 기준키보다 큰 데이터를 찾아 50을 선택하고, 마지막 데이터부터 기준키보다 작은 데이터를 찾아 5를 선택한다. 그리고 선택된 50과 5를 교환한다.
	② 계속해서 진행하여  기준키보다 큰 데이터인 40을 선택하고, 기준키보다 작은 데이터인 19를 선택한  후 두 수를 교환한다.
	③ 마찬가지로 진행하여 기준키보다 큰 데이터인 40과 기준키보다 작은 데이터인 9을 선택한다. 그런데 발견된 위치가 서로 교차하는데 이런 경우에는 두 값을 교환하지 않고 기준키 20과 작은 데이터인 9를 교환한다. 또한 기준키보다 큰 데이터를 발견하지 못하는경우에도 기준키와 작은 데이터를 교환한다.
	④ 데이터들을 보면 기준키 20을 기준으로 왼쪽에는 기준키보다 작은 데이터들이, 오른쪽에는 큰 데이터들이 있다. 이때 기준키를 중심으로 양분한다. 이제부터는 기준키를 중심으로 왼쪽 데이터들에 대해 그리고 오른쪽 데이터들에 대해 같은 방법으로 동작한다.
	[왼쪽 데이터들에 대해 동작하는 과정] ⑤ 기준키 9보다 큰 데이터인 18과 작은 데이터인 5를 선택하고 교환한다.  ⑥ 나머지도 마찬가지로 진행하여 정렬한다.  ● 5와 18이 교차하므로 5와 9의 자리를 바꿔준다. ●  5를 기준키로 또 퀵 정렬을 한다.
	[오른쪽 데이터들에 대해 동작하는 과정] ● 40을 기준으로 40보다 큰 50과 40보다 작은 25의 자리를 바꿔준다. ● 40보다 큰 50과 40보다 작은 25가 서로 교차되어져 40과 25의 자리를 바꾼다.

---

3. 퀵 정렬 알고리즘 

 

A[ ], p, r

A의 p부터 r까지의 전체 데이터가 있다. 

 

if (p < r) then {q = partition(A, p, r) }

p가 r보다 작으면 partition 분할을 한다. 분할한다는 것은 앞을 기준으로 계속 비교하여 큰 값, 작은 값 계속 맞교환을 해주다가 서로 교차하면 작은 값과 기준값이 서로 교환이 되면서 분할이 된다.

즉, 일정한 반복 횟수를 통해서 정렬을 하게 되면 기준키값을 기준으로 왼쪽 오른쪽으로 분리가 된다. 

 

quickSort(A, p, q-1)

A의 p부터 q-1까지가 되고, 

 

quickSort(A, q+1, r)

A의 q+1부터 r까지

	왜 q가 빠졌을까? A라는 배열 p와 r로 반으로 나눴을 때 중간에 q가 존재하면 앞의 데이터들은 q보다 하나 작으니깐 q-1이고, 뒤의 데이터들은 q보다 하나 많으니깐 q+1이 된다. 그래서 이것을 파티션으로 나뉜다음에 퀵 정렬을 하는데에 q를 제외한다. 왜냐하면 이렇게 교환된 상태는 q를 기준으로 해서 왼쪽은 q보다 작은값이 들어와있게돼고, 오른쪽은 q보다 큰값이 들어와있게된다. 이 q는 더이상 움직일 필요가 없기 떄문에 q는 굳이 고려하지 않아도 된다.
	q를 제외하고 q-1, q+1 까지 부분적인 배열들을 퀵 정렬을 통해서 다시 정렬한다.  그래서 위의 경우에도 재귀 호출(Recursive Call)이다. 퀵 정렬, 퀵 정렬 자기 자신을 재귀 호출한다. 그래서 이런걸 점화식형태로 표현할 수도 있고 재귀호출형태로도 표현할 수 있다.

 

 

partition(A[ ], p, r)

파티션 나누는 함수 

p부터 r 전체 데이터에 대해서 배열 A의 원소들을 A [r] 맨 끝을 기준으로 했다.

앞의 예제에서는 기준키를 맨 앞으로 잡았는데 해당 함수는 맨 끝을 기준으로 잡았다. 맨 앞이나 맨뒤나 어딜 기준키로 잡든 상관없다.

---

4. 퀵 정렬 복잡도

평균 수행 시간 (Average Case)

---

 

최악 수행 시간 (Worst Case)

---

병합 정렬과 퀵 정렬은 정렬하고자 하는 대상 데이터를 나누고 나뉜 데이터들을 반복적인 방법으로 정렬해 가는 방법이므로 재귀적인 정렬 알고리즘이라고 할 수 있다