정렬 - 퀵 정렬, 계수 정렬

퀵 정렬

• 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법

• 편향된 분할이 발생할 때 연산의 양이 O(N^2)

• c++의 algorithm 라이브러리에 sort() 함수는 퀵 정렬을 기반으로 하며 O(NlogN)을 보장

void quickSort(int start, int end)
{
  if (start >= end)
      return ;
  int key = start;
  int i = start + 1;
  int j = end,
  int temp;

  while (i <= j) // 재귀 시 진입방지 조건 
  {
      while (i <= end && a[i] <= a[key])
          i++;
      while (j > start && a[j] >= a[key])
          j--;
      if (i > j) // 엇갈리지 않았다면 두 값을 서로 바꿔줌
          swap(&a[key], &a[j])
      else // 엇갈렸으면 피봇값과 작은 값을 바꿔줌
          swap(&a[i], &a[j])
  }
  quickSort(start, j - 1);
  quickSort(j + 1, end);
}

 

 

 

계수 정렬

• 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘

• 각 데이터를 크기를 기준으로 바로 분류하므로 O(N)의 시간 복잡도를 가짐

• 데이터의 크기가 한정적일 때 사용할 수 있음 (MAX_VALUE가 필요하기 때문)

• 메모리를 많이 사용하는 게 단점
  ​

  #define MAX_VALUE 10001
  ​
  int n, m;
  int a[MAX_VALUE];
  ​
  int main()
  {
    scanf("%d", &n);
    for (int i = 0 ; i < n ; i++)
    {
        scanf("%d", &m);
        a[m]++;
    }
    for (int i = 0 ; i < MAX_VALUE ; i++)
    {
        while (a[i] != 0)
        {
            printf("%d", i);
            a[i]--;
        }
    }
  }