퀵 정렬
삽입 , 선택 , 버블 정렬의 경우 이중 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;
}