얼마 전 컴퓨터 동아리에 가입했다. ps는 파이썬으로밖에 안 해봤는데 C로 하는 연습도 좀 해 봐야겠다.
놀랍게도 지금은 교양 시험 일주일 전이다. 하지만 나에게는 토일월이 있다(라고 할 뻔)

병합 정렬(merge sort)

병합 정렬은 분할 정복(divide and conquer) 기법 중 하나이다.
분할: 배열을 각 부분의 크기가 1이 될 때까지 반으로 나눈다
정복: 나눠진 배열을 정렬하면서 합친다
이런 느낌이라고 보면 되겠다.

time complexity

배열을 나누고 합치는 데 n번 연산
이를 log n번 반복
-> 시간복잡도 O(nlogn)이다.

구현 방법

2개의 함수를 사용한다(poscat 피피티에 그렇게 나와 있다)
1. merge_sort(int arr[], int start, int mid, int end)
배열을 합치면서 정렬해주는 함수이다.
2개의 index를 만들어서 하나는 처음, 하나는 중간부터 시작하게 만든다.
대소를 비교하며 합치고 둘 중 하나라도 끝에 도달하면 나머지를 합친다. 이후 배열을 새 배열에 복사해준다.
2. merge_array(int arr[], int start, int end)
재귀함수이다. 배열 길이가 1이 될 때까지 나누는 데에 사용된다.

참고

배열을 함수의 매개변수로 사용하려면?

void func(int* arr)
void func(int arr[])

취향껏 골라 쓰시면 됨.

처음에 짰던 코드

//merge sort in C
#include <stdio.h>

void merge_sort(int arr[], int start, int mid, int end)
{
  if(start>=end)
    return;
  int arr_n[1000001]={};
  int i=start, j=mid+1, k=start;
  while(i<=mid && j<=end)
    {
    if(arr[i]<arr[j])
      arr_n[k++] = arr[i++];
    else
      arr_n[k++] = arr[j++];
    }
  //남은 요소들 넣어주기
  while(i<=mid)
    arr_n[k++] = arr[i++];
  while(j<=end)
    arr_n[k++] = arr[j++];
  //요소들을 새로운 배열로 복사
  for(k=start; k<=end; k++)
    {
      arr[k]=arr_n[k];
    }
}

void merge_array(int arr[], int start, int end)
{
  if(start>=end)
    return;
  int mid = (start+end)/2; 
  merge_array(arr, start, mid);
  merge_array(arr, mid+1, end);
  merge_sort(arr, start, mid, end);
}

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

이게 안 될리가 없는데(=O(n log n)인데) 계속 시간초과가 뜨는 거야
그래서 결국 챗지피티한테 이거 외않됨? 이라고 물어봤다.

그 결과
1. 초기 배열 크기를 고정시키지 말고 malloc을 써서 공간을 절약해라.

int *arr_n = malloc((end-start+1)*sizeof(int))

2. 요소들을 새로운 배열로 복사시키는 부분에서 시간을 많이 잡아먹는다.
   #include <string.h>를 쓰고

memcpy(&arr[start], arr_n, (end-start+1)*sizeof(int))

를 사용하면 된다.

Solution

//bubble sort in C
#include <stdio.h>

void bubble_sort(int arr[], int n)
{
  int i, j, temp;
  for(j=n-1; j>=0; j--)
  {
    for(i=0; i<j; i++)
    {
      if(arr[i]>arr[j])
      {
        
      }
    }
  }
}

int main()
{
  int n, i=0;
  int arr[1001]={};
  scanf("%d", &n);
  for(i=0; i<n; i++)
  {
    scanf("%d", &arr[i]);
  }
  bubble_sort(arr, n);
  for(i=0; i<n; i++)
    {
        printf("%d\n", arr[i]);
    }
}