합병 정렬, 퀵 정렬

퀵 정렬

• 삽입 , 선택 , 버블 정렬의 경우 이중 for문을 사용하여 배열을 정렬하는 기법

• 3가지의 정렬의 시간 복잡도는 이중 for문 이므로 O(n^2)

• 반면 퀵 정렬, 합병 정렬의 경우 시간 복잡도는 O(n*log n)

• 퀵정렬, 합병 정렬은 재귀함수를 사용한다.

합병정렬 구현

#include <stdio.h>
// 1 2  3 4      5 6 7 8 
// 1 2  3 4      5 6     7 8 
void sort_arr(int arr[] , int str1 , int end1 , int str2 , int end2);

void union_arr(int arr[] , int str , int end){
  if(str >= end){
   return;  
  }
  else{
  int mid = (str + end) / 2;
  union_arr(arr , str , mid);
  union_arr(arr , mid+1 , end);
  sort_arr(arr , str , mid , mid+1 , end);
  }
}

void sort_arr(int arr[] , int str1 , int end1 , int str2 , int end2){
  int tmp_str1 = str1;
  int tmp_str2 = str2;
  int tmp_arr[100001];
  int tmp_arr_id = 0;
  while(tmp_str1 <= end1 && tmp_str2 <= end2){
    if(arr[tmp_str1] > arr[tmp_str2]) {
      tmp_arr[tmp_arr_id++] = arr[tmp_str2++]; 
    }
    else tmp_arr[tmp_arr_id++] = arr[tmp_str1++];
  }
  if(tmp_str1 > end1){
    for(int i = tmp_str2 ; i <= end2 ; i++) tmp_arr[tmp_arr_id++] = arr[i];
  }
  else{
    for(int i = tmp_str1 ; i <= end1 ; i++) tmp_arr[tmp_arr_id++] = arr[i];
  }
  for(int i = str1 ; i<= end2 ; i++){
    arr[i] = tmp_arr[i-str1];
  }
}

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