[알고리즘] 4강 - 정렬(2)

✅ 1. 퀵 정렬

(1) 퀵 정렬 이란?

• 피벗(부분 배열로 분할하는 기준 데이터)을 기준으로 두 부분배열로 분할해서 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식을 의미함.
• ** 피벗은 보통 주어진 배열의 첫 번째 데이터로 지정함. **

(2) 퀵 정렬 - 원리

• 피벗: 배열의 첫 번째 데이터인 30을 지정해놓음.
• 해당 피벗을 기준으로 피벗 보다 작은 값은 왼쪽 큰 값은 오른쪽으로 정렬을 반복 하는 원리임.

(3) 퀵 정렬 - 전체적인 처리 과정

• 분할: 피벗이 제자리를 잡고 왼쪽과 오른쪽의 값을 크고 작은 값으로 단순히 나눈 과정
• ** 피벗을 정해놓고 분할함수를 통해서 계속해서 분할하면서 정렬하는 과정이 퀵 정렬임. **
• TIP: 피벗을 정해놓고 두개의 부분배열로 분할을 하면, 해당 두 개의 부분배열에는 각각 피벗을 또 정해서 반복을 함.

(4) 퀵 정렬 - 알고리즘

• 분할함수: 정해진 피벗의 위치를 찾아서 넣어주는 과정 및 왼쪽과 오른쪽 부분배열을 피벗보다 크고 작은 값으로 만들어주는 과정 및 함수로 볼 수 있음.
• ** 또한, 두 부분배열로 나누면 두개의 부분배열에는 각각의 피벗이 또 두개의 부분배열로 각각 나누는 과정을 진행함. **

• (1) if(n > 1): 배열의 데이터가 한 개 이상일 경우 조건문을 수행함.
• (2) pivot = Partition(A[], n): 배열을 받고, 해당 배열의 크기 n을 받아 내부적으로 피벗을 정해서 피벗을 기준으로 크고 작은 값들을 분할 해주고 최종적으로 피벗의 위치를 찾아서 거기에 피벗 데이터를 넣어주며, 마지막으로 pivot 의 인덱스를 리턴함.
• (3) Partition(): 순환 호출(재귀 호출)의 대상이 되며, 해당 함수를 통해서 A[0] 피벗을 기준으로 왼쪽 오른쪽 값을 나누며 피벗의 제자리를 찾아가 분할이 되는 과정을 처리해줌.
• (4) QuickSort(A[pivot-1], pivot,): 이전에 리턴 받은 pivot 의 인덱스를 기준으로 실제로 배열을 잘라서 왼쪽 부분배열에 대한 퀵 정렬을 순환 호출(재귀) 함.
• (5) QuickSort(A[pivot+1], n-pivot-1): 마찬가지로 pivot 인덱스를 기준으로 실제로 배열을 잘라서 오른쪽 부분배열에 대한 퀵 정렬을 수행함.
• TIP: 퀵 정렬을 수행하는 알고리즘에선 논리적이지 않고 실제로 물리적으로 배열을 슬라이싱해서 두 부분배열로 나눔.

• 위의 코드의 분할 과정이며, 왼쪽과 오른쪽 부분배열로 나눠서 최종적으로 피벗의 위치 인덱스를 리턴함.
• ** Left > Right 가 큰 경우에는 교환 보다는 일방적으로 피벗인 30을 Right 에 위치한 25와 교환을 하는 것임. **

(5) 퀵 정렬 - 처리 순서 예시 (핵심)

• 왼쪽 부분배열을 먼저 재귀호출을 하기 때문에 왼쪽 부분배열을 우선적으로 먼저 처리를 한 뒤, 다음 오른쪽 부분배열을 처리하게 된다.
• 이때 오른쪽 부분배열 또한 나누면 왼쪽 부분배열이 나오게 되는데 여기서도 왼쪽 부분배열을 먼저 처리하는 식으로 진행됨.
• ** 즉, 오른쪽으로 진행이 될 때 처리는 왼쪽 부분배열을 처리하는 원리로 반복적으로 정렬을 하는 원리임. **

(6) 퀵 정렬 - 성능과 특징

• 피벗과 비교하는 횟수: 각 데이터는 피벗과 1회 또는 많아야 2회씩 비교함. ( 2회씩 비교하는 경우는 데이터를 교환하는 과정에서 Left < Right 에 대한 비교를 통해서 바꿔도되는지 여부를 파악하고 바꾸는데 이럴 때 1회가 추가 됨. )
• Partition() 성능 결론: 입력 크기 n에 대해 수행하는 연산 수가 정확히 n에 비례하기 때문에 θ(n) 의 시간복잡도를 가짐.
• 빅오: 최악의 경우를 기준으로 이 정도보다 더 나빠지지 않는다는 상한선을 정해놓은 것을 의미함.
• 빅오메가: 최선의 경우를 기준으로 아무리 잘 돼도 이 정도는 걸린다는 하한선을 정해놓은 것을 의미함.
• ** 빅세타: 빅오(상한), 빅오메가(하한)을 만족하는 정확한 성장률로써, 해당 알고리즘의 정확한 속도로 볼 수 있음. **
• 즉, Partition() 함수의 경우 입력 데이터의 상태와 상관없이 항상 배열 전체를 한 번 훑어야만 일이 끝나기 때문에 θ(n) 임.

• QuickSort 재귀: 해당 재귀 자체는 점화식으로 T(n_L) 과 T(n_R) 로 표기 할 수 있으며, 해당 T(n_L), T(n_R) 은 분할된 두 부분배열의 데이터 크기로 볼 수 있음.
• 즉, 피벗을 제외한 정렬 할 데이터들은 n_L + n_R = n - 1 이 될 수 있음. (-1은 피벗은 정렬 부분배열 대상이 아니기 때문임)
• ** 또한, 최악의 경우 피벗을 가장 작은 값 또는 가장 큰 값으로 잡게 되면, 한쪽 부분 배열은 0개로 비어있게 되고 다른쪽 부분 배열은 n - 1 개의 부분 배열을 가지게 되므로, n - 1개에 대해서 처음부터 분할을 다시하는 꼴이 될 수 있음. **
• ** 이러한 최악과 최선을 모두 더한값이 평균적인 수행시간이 될 수 있음. **
• 결론: T(n) = T(n_L) + T(n_R) + θ(n) 이 될 수 있음.

(7) 퀵 정렬 - 성능과 특징 ( 최악의 경우 )

• 이미 정렬이 된 데이터인 경우 0:n-1 또는 n-1:0 으로 분할이 되게 됨.

• 입력 데이터가 정렬된 경우와 피벗을 배열의 첫 번째 원소로 정한 경우
• 이때, 피벗이 항상 최소값이나 최댓값이 되기 때문에 최악의 경우가 될 수 있음.
• θ(n) 자체는 피벗이 제자리를 찾아가는 그 시점까지의 연산량을 의미할 수 있다.

단계	수행하는 일(θ 관점)	재귀 호출 (T 관점)
1단계	n개를 훑어서 피벗 1개 고정	T(n - 1)
2단계	n - 1 개를 훑어서 피벗 1개 고정	T(n - 2)
3단계	n - 2 개를 훑어서 피벗 1개 고정	T(n - 3)
...	...	...
합계	n + (n - 1) + (n - 2) + ... + 1	O(n^2)

• 표를 통해 예를 들면, 위와 같이 입력 데이터 정렬된 경우 제일 첫 번째 값을 피벗으로 지정한다고 가정하면, 피벗이 제자리를 찾아가고 남은 데이터는 결국 n - 1 개의 데이터들이 남기 때문에 이후에 n - 1, n - 2, n - 3 ... 반복적으로 재귀호출을 하면서 피벗을 제자리에 넣으며 정렬을 하게 된다.
• 이 경우에서 재귀 호출을 포함한 모든 연산 횟수를 계산하면 결국 n + (n - 1) + (n - 2) + ... 1 을 다 더했을 때 n^2 이 됨.

1층: ■■■■■■ (n개)
2층: ■■■■■ (n-1개)
3층: ■■■■ (n-2개)
4층: ■■■ (n-3개)
...
n층: ■ (1개)

=> n x n / 2 = n^2/2 ( 최고차항: n^2 )

• 이유는, 등차수열의 합 원리를 통해 구하게 되면 n-1, n-2 .. 데이터를 재귀호출 관점에서보면 직각삼각형의 모습을 띄게 되는데, 이때 결국 전체 면적이 블록의 총 개수가 되기 때문에 직각삼각형의 넓이를 구하고, 최고차항을 보면 n^2 이 됨.
• 결과 시간복잡도: O(n^2)

(8) 퀵 정렬 - 성능과 특징 ( 최선의 경우 )

• 피벗이 제자리를 잡고 부분배열로 분할하는 과정이 n/2:n/2 (왼쪽, 오른쪽 부분배열) 로 나눠지는 경우가 이상적인 경우임.

• 피벗이 항상 중간값이 되는 경우이기 때문에 해당 점화식을 풀면 O(nlogn) 의 시간복잡도를 구할 수 있음.

(9) 퀵 정렬 - 성능과 특징 ( 평균 수행시간 )

•  ** 퀵 정렬의 평균 수행시간은 O(nlong) 이며, 이유는 수학적으로 피벗이 매번 최댓값이나 최솟값으로만 뽑힐 확률은 극히 낮고, 설령 몇 번 나쁘게 뽑히더라도, 단 한 번만 중간쯤 되는 피벗이 뽑히면 리스트 크기가 확 줄어들면서 균형이 맞기 때문임. **

• 피벗 선택을 임의로 선택이 보장되면, 평균 수행시간을 O(nlogn) 으로 보장이 가능해짐.
• 피벗을 배열의 첫 번째 원소로 지정함과 동시에 배열이 정렬된 경우가 결국 최악의 수행시간을 보장하기 때문에, 이를 해결하면 평균 수행시간인 O(nlogn) 으로 보장이 가능해짐.
• ** 즉, 일반적으로 해결을 하기 위해서는 피벗을 첫 번째 원소가 아닌 랜덤값(임의의 값)을 선택한 후, 배열의 첫 번째 원소와 서로 교환한 후 정렬을 수행함. ** 
• 제자리 정렬 알고리즘: 입력 배열 이외에 추가적인 저장 공간을 상수개만 사용하기 때문에 제자리 정렬 알고리즘임.

• 안정적이지 않은 정렬 알고리즘: 동일한 값이 상대적으로 위치가 바뀔 수 있기 때문에 안정적이지 않은 정렬 알고리즘임.

• ** 분할정복 방법이 적용이 되었으며, 분할정복 방법이 되면 기본적인 형태가 순환 알고리즘 형태로 되며, 순환 알고리즘의 성능은 점화식으로 표현이 됨. **

---

✅ 2. 합병 정렬

(1) 합병 정렬 이란?

 

• 입력 배열을 두 부분배열로 반복적으로 분할을 시키고, 분할 된 부분 배열들을 합병 시키는 과정에서 정렬을 하는 방식임. 

(2) 합병 정렬 - 전체적인 수행 과정

• 분할: 합병 정렬은 더 이상 나눌 수 없을 때까지(원소가 1개가 될 때까지) 쪼개는 분할 작업을 먼저 진행함.
• 합병: 분할 된 원소 1개짜리 부분 배열을 합병 하는 과정에서 데이터를 정렬하면서 합병을 하게 됨.

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

• 순환 알고리즘으로, 분할정복 방법을 활용한 케이스이다.
• ** MergeSort() 재귀 호출로 부분배열의 크기인 n이 1이 될 때 까지 오른쪽 부분배열과 왼쪽 부분배열을 나눠서 쪼갠 뒤 조건문에 의해서 더 이상 쪼갤 수 없다고 판단이 되면, Merge() 함수를 호출해 두 부분배열을 정렬하면서 합병을 하게 됨. **
• 쉽게 말해, MergeSort() 재귀호출 단계에서는 왼쪽 하위 그룹이 먼저 완전히 분할이 되고 합쳐진 뒤에 오른쪽 분할이 일어나고 합쳐지는 과정이 된다.
• ** 즉, 8개 데이터가 있다고 가정하면, 4개로 쪼개고 다시 왼쪽 2개로 쪼개고 다시 왼쪽 1개로 쪼개고 이 쪼개진 1개와 1개를 합병과정을 통해서 2개를 합쳐서 2개의 정렬된 배열로 만들고, 다음으로 2개와 2개를 합쳐서 4개의 정렬된 배열로 만들고, 이후에 오른쪽 4개의 부분 배열을 왼쪽을 기준으로 또 쪼개고 합병을 하는 과정을 반복함. **

(4) 합병 정렬 - 알고리즘 ( Merge() 함수의 동작 )

• Merge() 함수는 분할 된 데이터를 합병을 시켜주는 역할을 해줌.

• 합병 과정에서는 분할 된 두 부분배열에 대해서 앞에서 부터 차례로 서로 비교를 하면서 배열에 정렬을 하게 됨.

• 부분 배열 B, C 가 있다고 하면, 결과 배열에 두 부분배열을 비교한 값들을 비교를 통해서 정렬을 하게 됨.

(5) 합병 정렬 - 성능과 특징

• Merge() 함수의 수행시간은 두 부분배열 B[], C[] 간의 비교 횟수이기 때문에 최소 n/2 번 이며, 많아야 n - 1 번 비교를하게 됨.
• 즉, Merge() 함수는 최선과 최악 둘 다 n의 시간복잡도를 가지기 때문에 θ(n) 의 시간복잡도를 가질 수 있음.

• 순환 알고리즘의 성능은 점화식으로 표현을 하기 때문에, 데이터 n개를 정렬하는데 걸리는 시간을 T(n) 으로 놓고 보았을 때, 왼쪽 절반 n/2 개를 합병 정렬하는데 걸리는 시간이므로, T(n/2) 로 보고 오른쪽도 마찬가지로 절반 n/2 개를 합병 정렬하는데 걸리는 시간이므로, T(n/2) 로 볼 수 있음.
• 또한, Merge() 함수는 θ(n) 의 시간복잡도를 가지므로, 결론은 T(n) = 2T(n/2) + θ(n) 으로 볼 수 있음.
• ** 결론은 T(n) = O(nlogn) 이 되게 됨. **

• 안정적인 정렬 알고리즘: 합병 과정에서 동일한 두 데이터가 있을 때 항상 왼쪽 데이터를 먼저 선택해 정렬하기 때문임.
• 제자리 정렬 알고리즘이 아님: 왼쪽 부분배열과 오른쪽 부분배열을 정렬하기 위해서 결과 배열을 만들어서 데이터를 삽입하기 때문에 입력 크기 n만큼의 추가적인 저장공간을 요구하게 됨.
• 전형적인 분할정복 방법이 적용됨: 분할, 정복, 겹합의 과정을 모두 거치기 때문임.

(6) 합병 정렬 - 비순환적 방식의 합병 정렬

• 반드시 순환 알고리즘을 사용하지 않고도, 반복문을 통해서 합병 정렬 알고리즘을 구현 할 수 있음.
• 분할 과정을 거치지 않고, 합병만으로도 가능하긴하다는 말임.