알고리즘 study -13-

더 빠른 속도의 정렬

---

• 합병 정렬 : 재귀호출, 혹은 재귀적 구조를 이용한 정렬
• 퀵 정렬 : 재귀호출, 혹은 재귀적 구조를 이용한 정렬
• 힙 정렬

-->> O(nlogn) 만에 정렬 가능!!

---

<로그?>

-> 지수함수의 역함수

보통 컴퓨터 공학에서 log를 쓰는 경우 그 밑이 2이므로, 보통 밑을 생략

log x = 2를 몇 번 곱해야 x가 되는가

대략 log 10^100 = 332.198
-> log는 수의 값을 대폭 감소 시킨다

---

O(logn) = 굉장히 빠른 시간복잡도

---

<합병 정렬 Merge Sort>

-> 배열을 절반으로 나누어 각각을 정렬한 후, 합친다

• T(n) -> n개의 숫자를 합병정렬 할 때의 시간복잡도

1. 왼쪽 합병정렬 -> T(n/2)
2. 오른쪽 합병정렬 -> T(n/2)
3. 합친다 -> O(n)

T(1) = 1

T(n) = 2 * T(n/2) + O(n) = 2(2T(n/4) + O(n/2)) + O(n)
= 4T(n/4) + 2O(n)
= 8T(n/8) + 3O(n) = ....

n/2^k 가 1이 될때 까지 -> n = 2^k 될때 까지

---

-->> k = logn

---

위식 정리 해보면 T(n) = n * O(1) + O(nlogn)

---

<합병정렬의 재귀함수 디자인>

재귀함수 디자인 과정

1. 작성하려는 함수의 역할 말로 정의
2. 함수가 기저조건에서 제대로 작동하게 작성
3. 함수가 제대로 동작한다고 가정하고 함수를 완성
4. 함수 완성 후, 기저조건으로 수렴함을 보인다

---

1. void mergeSort(int arr[], int s, int e) : arr을 s부터 e까지 정렬하는 함수

2. 기저조건 = 원소 1개 있을 때
   if(s >= e) return;

3. 함수 작성

void mergeSort(int arr[], int s, int e){
	if(s>=e){
    	   return;
        }
       	mid = (s+e) / 2;
        
        mergeSort(arr, s, mid);
        mergeSort(arr, mid+1, e);
        
        merging(s, mid, mid+1, e);  // 함수 따로 만들기
        
        // s ~ mid = 왼쪽 절반  &  mid+1 ~ e = 오른쪽 절반
}

4. 합병정렬 최종 구현

#include <stdio.h>

void merging(int arr[], int s1, int e1, int s2, int e2);

void mergeSort(int arr[], int s, int e){
  // arr의 s 부터 e 까지를 합병 정렬
  
  if(s >= e)
    return;  // 원소 1개인 경우
  else{
    
    int mid = (s+e) / 2;
    
    mergeSort(arr, s, mid);
    mergeSort(arr, mid+1, e);
    
    merging(arr, s, mid, mid+1, e);
     
  }
  
}

void merging(int arr[], int s1, int e1, int s2, int e2){
  // arr의 s1~e1이 왼쪽 절반, s2~e2가 오른쪽 절반일 때,
  // 이 둘을 합쳐서 s1 ~ e2를 정렬된 겨로가로 만드는 함수
  
  int p, q; // 현재 최솟값 가리키는 변수
  int temp[100];
  int temp_idx = 0;
  
  p = s1;
  q = s2;
  
  while(p <= e1 && q <= e2){ // 범위 안에 있을때 까지만
    if(arr[p] <= arr[q]){
      temp[temp_idx++] = arr[p];
      p++;
    }
    else{
      temp[temp_idx++] = arr[q];
      q++;
    }
  }
  
  if(p>e1){  // 오른쪽만 남았으므로 차례로 넣는다
    for(int i = q; i<=e2; i++){
      temp[temp_idx++] = arr[i];
    }
  }
  else{ // 왼쪽만 남았으므로 차례로 넣는다
    for(int i=p; i<=e1; i++)
      temp[temp_idx++] = arr[i];
  }
  
  // 이제 temp는 완성
  // temp 값 복사해서 arr에 넣기
  
  for(int i = s1; i <= e2; i++){
    arr[i] = temp[i - s1]; // temp는 0인덱스 부터 선언했으므로!
  }
  
}

int main() {

  int n;
  int numbers[100];
  
  scanf("%d", &n);
  
  for(int i = 0; i <n; i++)
    scanf("%d", &numbers[i]);
    
  mergeSort(numbers, 0, n-1);
  
  for(int i = 0; i<n; i++)
    printf("%d ", numbers[i]);

  return 0;
}

---

<퀵 정렬 Quick Sort>

-> 원소를 하나 정하여, 해당 원소보다 작은 수들과 큰 수들로 나눈다

pivot 정해서 왼쪽은 pivot보다 작거나 같은 값
오른쪽은 pivot 보다 큰 값

---

1. pivot의 위치는 변하지 않는다
2. pivot의 왼쪽 영역과 오른쪽 영역의 자리가 바뀌지 않는다
   -> 왼쪽, 오른쪽 정렬을 각각 따로 해도된다

---

1. pivot 정하기
2. 작거나 같은 값과 큰 값을 분류한다
3. 각각을 퀵정렬 한다

---

T(n) = T(left) + T(right) + O(n)

O(n) : pivot보다 작거나 같은 값과 큰 값 분류
left : pivot 보다 작거나 같은 원소 개수
right : pivot 보다 큰 원소 개수

---

퀵정렬은 평균적으로 O(nlogn)이 걸린다고 말한다
정확히 nlogn은 아니다

최악의 경우 O(n^2)
ex> -> 이미 오름차순/내림차순으로 정렬되어 있는 경우

---

퀵소트 구현

#include <stdio.h>

int getLeft(int arr[], int start, int end, int pivot, int result[]){
  // arr의 start 부터 end 까지 숫자들 중에서
  // pivot 보다 작거나 같은 값을 result에 채우는 함수
  // 또한, 위와 같은 원소의 개수 반환
  
  int index = 0;
  
  for(int i = start; i <= end; i++){
    if(arr[i] <= pivot)
      result[index++] = arr[i]; 
  }
  
  return index;
}

int getRight(int arr[], int start, int end, int pivot, int result[]){
  // arr의 start 부터 end 까지 숫자들 중에서
  // pivot 보다 큰 값을 result에 채우는 함수
  // 또한, 위와 같은 원소의 개수 반환
  
  int index = 0;
  
  for(int i = start; i <= end; i++){
    if(arr[i] > pivot)
      result[index++] = arr[i]; 
  }
  
  return index;
}

void quickSort(int arr[], int start, int end){
  // arr을 start 부터 end 까지 퀵정렬하는 함수
  
  if(start >= end)
    return;
  
  int pivot = arr[start];
  int left[100], right[100];
  
  int left_cnt = getLeft(arr, start + 1, end, pivot, left);
  int right_cnt = getRight(arr, start + 1, end, pivot, right);
  
  // ex> 4 8 2 2 1 7 6 2 3 
  // pivot = 4
  // left = 2 2 1 2 3 
  // right = 8 7 6
  
  // left, right 원소 개수 필요  /  pivot 기준으로 arr 정렬
  for(int i = 0; i < left_cnt; i++){ //  피봇 왼쪽 넣기
    arr[i+start] = left[i];
  }
  
  arr[start+left_cnt] = pivot; // 피봇 넣기
   
  for(int i = 0; i <right_cnt; i++){
    arr[start+left_cnt+1+i] = right[i]; // 오른쪽 넣기
    // start 에서 왼쪽원소 다 넣고 피봇 하나 넣고 다음 위치 부터 오른쪽 넣기
  }
  
  //재귀
  quickSort(arr, start, start+left_cnt-1);  // pivot 전후로
  quickSort(arr, start+left_cnt+1, end);
  
}

int main() {
  
  int n;
  int arr[100];
  
  scanf("%d", &n);
  
  for(int i = 0; i<n; i++)
    scanf("%d", &arr[i]);
    
  quickSort(arr, 0, n-1); 
  
   for(int i = 0; i<n; i++)
    printf("%d ", arr[i]);

  return 0;
}

---