[C] Quicksort 정렬하기

백준 2751번 수정렬하기 2번을 푸는데 quicksort를 이용하여 풀려고 했다.

근데 quicksort는 최악의 경우 시간복잡도가 n^2이기때문에 시간초과가 떴다...

다음번에는 mergesort를 이용하여 다시 풀어봐야겠다.

아래의  소스코드는 quicksort를 이용해 시간이 정해져있지 않을때 맞는 코드이다..

또 공부해야한다니..

 

#include <stdio.h>
#include <string.h>

void swap(int *a, int *b) //포인터를 써야지 값이 함수를 넘어가도 유지가 됨
{ 
  int tmp;
  tmp=*a;
  *a=*b;
  *b=tmp;
}

void quicksort(int arr[],int left,int right)
{
  if(left==right) //탈출 조건(원소가 하나일때)
    return;
  int pivot=left;
  int i=left+1,j=right; //i는 pivot보다 크면 stop
  while(1) 
    {
      while(arr[i]<arr[pivot]&& i<=right) // 4, 3의 경우 i가 범위를 넘어갈 수 있음
        {
          i++;
        }
      while(arr[j]>arr[pivot] ) //두개가 같으면 범위를 넘어갈 수 있음
        {
          j--;
        }
      if(i>=j) //둘이 교차하면 j는 pivot보다 작은 수 일수밖에 없음
        //i가 pivot보다 작으면 안바꾸고 지나가니까 j는 결국 pivot다는 작게됨
      {
        swap(&arr[pivot],&arr[j]); //j와 pivot 이 같은 곳을 가리켜도 어차피 같음
        break;
      }
      else
        swap(&arr[i],&arr[j]);
    }
  if(j!=left) //완쪽 구역이 남아있지 않을때
    quicksort(arr,left,j-1); //왼쪽 구역에서 다시 탐색
  if(i<=right) //오른쪽 구역이 남아있지 않을때
    quicksort(arr,i,right); //오른쪽 구역에서 다시 탐색
}

int main(void)
{
 int n;
  scanf("%d",&n);
  int arr[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\n",arr[i]);
    }
}