알고리즘(4) - 퀵정렬, 병합정렬 (Quick sort, Merge sort)

안녕하세요.

 

오늘은 이전에 배운 선택정렬, 삽입정렬, 버블정렬에 이어 분할정복이라는 개념을 적용하여 사용되는 퀵정렬과 병합정렬에 대해서 알아보려고 합니다.

 

 

분할 정복 ( Devide and Conquer )

 

분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식입니다.

 

분할 정복법은 분할 - 정복 - 결합의 과정을 거칩니다.

 

자세히 말하면, 큰 문제를 작은 문제로 분할(divide)하고, 작은 문제를 하나하나 해결(conquer)하고, 해결된 문제를 하나의 큰 문제로 결합(combine)하는 과정입니다.

 

분할정복의 장점

• 어려운 문제를 작은 문제로 나눔으로써 쉽게 해결합니다.
• 작은 문제를 분할하여 같은 작업을 더 빠르게 처리합니다.
• 병렬로 문제를 해결할 수 있습니다.

분할정복의 단점

• 함수를 재귀적으로 호출한다는 점에서 호출로 인한 오버헤드가 발생할 수 있습니다.
• 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버 플로우가 발생하거나 과도한 메모리를 사용하게 됩니다.

❄️ 오버헤드 : 오버헤드(overhead)는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말합니다.

스택 오버 플로우 : Stack Overflow는 Stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생합니다.

 

 

퀵정렬 ( Quick sort )과 병합 정렬 ( Merge sort )

 

분할정복 전략을 사용하는 알고리즘입니다.

 

퀵소트, 머지소트 -> 분할정복 전략을 사용하는 방법이 다릅니다.

 

- 퀵소트 : 분할 단계가 중요합니다.

- 병합소트 : 결합 단계가 중요합니다.

 

 

퀵정렬

 

1. 분할

 

- 배열에서 아무 요소나 골라서 그 값을 기준으로 분할합니다. - 이 기준이 피벗(pivot) 입니다.

- 피벗을 결정하는 로직은 하나여야만 합니다.

- 피벗보다 작거나 같은 요소는 피벗의 왼쪽으로 분할합니다.

- 피벗보다 큰 요소는 피벗의 오른쪽으로 분할합니다.

- 피벗을 기준으로 나뉜 요소들은 정렬되어 있지 않습니다.

 

예시 )  배열array(p…r)을 분할 합니다.

 

2. 정복

 

- 피벗을 설정하고 피벗을 기준으로 왼족,오른쪽으로 분할하여 재귀적으로 정렬하는 것을 정복이라고 합니다.

 

예시 ) `array[p..q-1]` (피벗보다 작거나 같은, 즉 피벗의 왼쪽에 있는 모든 요소들)과 `array[q+1..r]` (피벗보다 큰, 즉 피벗의 오른쪽에 있는 모든 요소들)을 재귀적으로 정렬하여 정복합니다.

 

 

퀵소트 특징

 

• 데이터를 정렬하는 알고리즘 중 하나입니다.
• 데이터를 대소그룹의 둘로 나누어 분할 한 후 전체를 정렬하는 방식의 알고리즘 입니다.
• 실행속도가 빠릅니다.
• 대량데이터를 정렬할때 많이 사용합니다.
• 정렬 알고리즘 중에서도 사용빈도가 높습니다.

---

퀵정렬도 예시를 들어서 살펴보면 왜 위에서 분할 단계가 중요하다고 했는지 알 수 있습니다.

 

[3,7,2,5,8,1,9] 라는 리스트가 존재할 때를 가정하고 한번 살펴볼게요.

 

여기서 우리는 가장 왼쪽의 노드를 피벗으로 설정하고 어떻게 퀵정렬이 이루어지는가를 보겠습니다.

 

1) pivot = 3 :

 

[2,1] [3] [7,5,8,9] 으로 분할이 이루어 집니다.

--> 위의 왼쪽 오른쪽으로 분할된 값은 보이듯이 정렬되지 않은 상태입니다.

 

pivot인 3은 자리가 확정되고 그를 제외한 리스트에서 각각 다시 분할이 이루어집니다.

 

2-1) pivot = 2

 

[1] [2] [3] [7,5,8,9] -- 왼쪽 리스트에서 pivot은 2가 되어 비교 후 교환이 이루어집니다.

 

2-2 ) pivot = 7

 

[1] [2] [3] [5] [7] [8,9] -- 오른쪽 리스트에서 pivot은 7이 되어 분할이 이루어집니다.

 

3) pivot = 8

 

[1] [2] [3] [5] [7] [8] [9] 이렇게 최종적으로 정복이 됩니다.

 

---

위의 예시를 보시면 아시겠지만

 

퀵정렬은 주어지는 입력 데이터의 상태가 어떤가에 따라서 시간복잡도의 차이를 보입니다.

 

** 분할 정복에서 시간 복잡도는 (최종 배열의 개수 * 반복 호출되는 횟수) 로 구할 수 있습니다.

 

정렬이 잘 되어 있는 경우 : O(NlogN)

-- 병렬적으로 분할과 정복이 이루어지면서  logN 번의 반복 호출 * 최종 n 개의 배열로 정렬이 이루어집니다.

 

정렬이 잘 안되어 있는 경우 : O(N^2)

-- 재귀호출과 같이 한 노드씩 분할 하는 것으로 분할을 n번 진행하고 최종 n개의 배열을 가집니다.

 

 

 

병합정렬

 

: 입력 배열을 같은 크기의 2개 부분 배열로 분할합니다. ( 이진 검색과 비슷한 방법입니다. )

 

1. 분할

 

 - 리스트를 반반씩 분할합니다.

 - 말그대로 분할만 될뿐 정렬이 이루어지지 않습니다.

 

2. 정복

 

- 분할 단계에서 만들어진 하위 문제 각각에 잇는 배열을 재귀적으로 정렬합니다.

 

 

3. 결합

 

- 정렬된 두 하위 배열을 하나의 정렬된 하위 배열로 결합합니다. ( 퀵소트와 다르게 분할되면서 정렬이 이루어지지 않고 결합단계에서 정렬이 이루어집니다.)

 - 예를 들면 왼쪽 리스트와 오른쪽 리스트의 첫번째 값을 비교하고 작은 값을 다음 리스트(임시배열)에 추가합니다.

 - 그 뒤에 낮은 값을 순서대로 임시 배열에 추가하여 다음 리스트로 반환합니다.

 - 아래의 combine 되는 예제를 눈으로 확인하면서 이해해보세요.

 

 

병합 정렬 장점

- 시간복잡도 O(nlogn)입니다.

 

병합 정렬 단점

- 임시 배열이 필요합니다. ( 주어진 메모리 이외에 저장할 배열이 필요합니다. )

 

 

병렬 정렬에 대해서 원리에 대해 실습해볼 수 있는 사이트를 남겨 놓을 테니 필요하신 분은 들어가셔서 한번 적용해보시면 좋을 것 같습니다.

(https://www.101computing.net/merge-sort-algorithm/)