2020.07.24 백준 2751번 수 정렬하기 2

단순히 수를 정렬하는 문제다.

수의 개수 N(1 ≤ N ≤ 1,000,000)이다.

 

그래서 퀵소트를 썼는데 시간초과가 떴다ㅜㅜ

 

1차 시도

#include <stdio.h>
#include <stdlib.h>

int divide(int *arr, int left, int right)
{
  int pivot;
  int low = left + 1;
  int high = right;
  int temp;
  
  pivot = arr[left];
  while(low <= high)
  {
    while (low <= right && pivot > arr[low])
    {
    low++;
    }
    while (high >= (left + 1) && pivot < arr[high])
    {
      high--;
    }
    if (low <= high)
    {
      temp = arr[low];
      arr[low] = arr[high];
      arr[high] = temp;
    }
  }
  temp = arr[left];
  arr[left] = arr[high];
  arr[high] = temp;
  return (high);
}

void  quicksort(int *arr, int l, int r)
{
  int pivot;
  if(l <= r)
  {
    pivot = divide(arr, l, r);
    quicksort(arr, l, pivot - 1);
    quicksort(arr, pivot + 1, r);
  }
}

int main(void) {
  int n;
  int i = 0;
  int *temp;
  
  scanf("%d", &n);
  temp = (int *)malloc(sizeof(int) * n);
  while (i < n)
  {
    scanf("%d", &temp[i]);
    i++;
  }
  quicksort(temp, 0, n - 1);
  for (i=0;i<n;i++)
  {
    printf("%d\n",temp[i]);
  }
  return 0;
}

 

질문 검색을 해보니 머지 소트를 써야된다고 써있었다.

머지 소트...이렇게 또 하나 알아간다.

 

2차 시도(성공)

#include <stdio.h>
#include <stdlib.h>

int n;
int size;
int *sorted;

void merge(int a[], int m, int middle, int n)
{
  int i = m;
  int j = middle + 1;
  int k = m;

  while (i <= middle && j <= n)
  {
    if (a[i] <= a[j])
    {
      sorted[k] = a[i];
      i++;
    }
    else
    {
      sorted[k] = a[j];
      j++;
    }
    k++;
  }
  if(i > middle)
  {
    for (int t = j; t <= n; t++)
    {
      sorted[k] = a[t];
      k++;
    }
  }
  else
  {
    for (int t = i; t <= middle; t++)
    {
      sorted[k] = a[t];
      k++;
    }
  }
  for(int t = m; t <= n; t++)
  {
    a[t] = sorted[t];
  }
}

void mergesort(int a[], int m, int n)
{
  int middle = (m + n) / 2;
  if(m < n)
  {
    mergesort(a, m, middle);
    mergesort(a, middle + 1, n);
    merge(a, m, middle, n);
  }
}

int main(void) {
  int i = 0;
  int *temp;
  
  scanf("%d", &n);
  temp = (int *)malloc(sizeof(int) * n);
  sorted = (int *)malloc(sizeof(int) * n);
  while (i < n)
  {
    scanf("%d", &temp[i]);
    i++;
  }
  mergesort(temp, 0, n - 1);
  for (i=0;i<n;i++)
  {
    printf("%d\n",temp[i]);
  }
  return 0;
}

아직 잘 몰라서 거의 베꼈는데 몇번 더 써보면서 익혀야겠다.