Introsort

설명

• 인트로 정렬(introsort)은 평균적으로 빠른 성능을 내면서 최악의 조건에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다.

• C++ STL에서 기본적으로 제공되는 정렬 함수이다.

• 퀵 정렬, 힙 정렬, 삽입 정렬을 합하여 정렬하는 알고리즘이다.

  • 3가지 알고리즘의 장점을 합쳐 각 정렬의 단점을 보완하고 최악의 경우를 대비한다.

• 인트로 정렬이 사용하는 이 3가지 알고리즘들은 비교 정렬이기 때문에 인트로 정렬 또한 비교 정렬이다.

  • 비교 정렬 : 정렬 알고리즘의 일종으로 두 값을 비교하는 것에 기반한다.

• 최악 시간 복잡도는 O(n log n), 평균 시간 복잡도 또한 O(n log n)이다.

  • 최선의 경우에는 퀵 정렬의 최선의 시간 복잡도와 같고, 최악의 경우에는 힙 정렬의 최악의 시간 복잡도와 같다. 즉, 항상 O(n log⁡ n)이다.

원리

• 퀵 정렬로 시작한 다음 재귀 깊이가 정렬 대상 요소의 수의 레벨(로그)을 초과할 때 힙 정렬로 전환하며 요소들의 수가 특정 임계치 미만일 때 삽입 정렬로 전환한다.

• 의사 코드는 아래와 같다.

  procedure sort(A : array):
      maxdepth ← ⌊log2(length(A))⌋ × 2
      introsort(A, maxdepth)
  
  procedure introsort(A, maxdepth):
      n ← length(A)
      if n < 16:
          insertionsort(A)
      else if maxdepth = 0:
          heapsort(A)
      else:
          p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
          introsort(A[1:p-1], maxdepth - 1)
          introsort(A[p+1:n], maxdepth - 1)

구현

• 설명

  1. 리스트의 크기가 16 이하라면 삽입 정렬을 한다.
  2. 전체 리스트에 대해 퀵 정렬을 수행한다.
  3. 수행 도중 재귀 호출의 깊이가 2log⁡n을 넘어가게 되면 4번 항목으로 넘어간다.
  4. 쪼개진 부분 리스트의 크기가 16 이하라면 그대로 놔둔다.
     16보다 크다면 해당 부분 리스트에 대해 힙 정렬을 수행한다.
  5. 3, 4번 항목이 모두 완료된 후, 대부분 정렬이 된 전체 리스트에 대해 삽입 정렬을 수행한다.

• 코드 : C++ 기반으로 구현한 코드

  void __swap(int * a, int * b) 
  {
      int tmp = * a;
      * a = * b;
      * b = tmp;
  }
  
  void __makeHeap(int *arr, int left, int right) 
  {
      for(int i=left; i<=right; i++) 
      {
          int now = i;
          while(now > 0) 
          {
              int par = now-1>>1;
              if(arr[par] < arr[now]) __swap(arr+par, arr+now);
              now = par;
          }
      }
  }
  
  void __heapSort(int *arr, int left, int right) 
  {
      __makeHeap(arr, left, right);
      for(int i=right; i>left; i--) 
      {
          __swap(arr, arr+i);
          int left = 1, right = 2;
          int sel = 0, par = 0;
          while(1) 
          {
              if(left >= i) break;
              if(right >= i) sel = left;
              else 
              {
                  if(arr[left] < arr[right]) sel = right;
                  else sel = left;
              }
              if(arr[sel] > arr[par]) 
              {
                  __swap(arr+sel, arr+par);
                  par = sel;
              } 
              else break;
              
              left = (par<<1) + 1;
              right = left+1;
          }
      }
  }
  
  void __insertionSort(int arr[], int left, int right) 
  {
      for(int i=left; i<right; i++) 
      {
          int key = arr[i+1];
          int j;
          for(j=i; j>=left; j--) 
          {
              if(arr[j] > key) arr[j+1] = arr[j];
              else break;
          }
          arr[j+1] = key;
      }
  }
  
  void __quickSort(int arr[], int left, int right, int depth) 
  {
      if(depth == 0) 
      {
          int size = right-left+1;
          if(size > 16) 
          {
              __heapSort(arr, left, right);
          }
          return;
      }
  
      int i = left, j = right;
      int pivot = arr[(left + right) / 2];
      int temp;
      do 
      {
          while (arr[i] < pivot)
              i++;
          while (arr[j] > pivot)
              j--;
          if (i<= j) 
          {
              __swap(arr+i, arr+j);
              i++;
              j--;
          }
      } 
      while (i<= j);
  
      if (left < j)
          __quickSort(arr, left, j, depth-1);
  
      if (i < right)
          __quickSort(arr, i, right, depth-1);
  
  }
  
  void introSort(int arr[], int n) 
  {
      int limit = 2*ceil(log2(n));
      if(n <= 16)
      {
          __insertionSort(arr, 0, n-1);
          return;
      }
      __quickSort(arr, 0, n-1, limit);
      __insertionSort(arr, 0, n-1);
  }

• 코드 : C# 기반으로 구현한 코드

  class main
    {
        static void Main(string[] args)
        {
            TestIntroSort sort = new TestIntroSort();
            int[] arr = new int[6] { 3, 4, 5, 2, 1, 10 };
  
            sort.IntroSort(arr, 6);
  
            for (int i = 0; i < arr.Length; ++i)
            {
                Console.WriteLine(arr[i]);
            }
            Console.ReadLine();
            
            /*
            1
            2
            3
            4	
            5
            10
            */
        }
    }
  
    class TestIntroSort
    {
        void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
  
        void MakeHeap(int[] arr, int left, int right)
        {
            for (int i = left; i <= right; ++i)
            {
                int now = i;
                while (now > 0)
                {
                    int par = (now - 1) / 2;
                    if (arr[par] < arr[now])
                        Swap(ref arr[par], ref arr[now]);
                    now = par;
                }
            }
        }
  
        void HeapSort(int[] arr, int left, int right)
        {
            MakeHeap(arr, left, right);
  
            for (int i = right; i > left; --i)
            {
                Swap(ref arr[0], ref arr[i]);
  
                int sel = 0, par = 0;
  
                while (true)
                {
                    if (left >= i)
                        break;
                    if (right >= i)
                        sel = left;
                    else
                    {
                        if (arr[left] < arr[right])
                            sel = right;
                        else
                            sel = left;
                    }
                    if (arr[sel] > arr[par])
                    {
                        Swap(ref arr[sel], ref arr[par]);
                        par = sel;
                    }
                    else break;
  
                    left = par * 2 + 1;
                    right = left + 1;
                }
            }
        }
  
        void InsertionSort(int[] arr, int left, int right)
        {
            for (int i = left; i < right; ++i)
            {
                int key = arr[i + 1];
                int j;
                for (j = i; j >= left; --j)
                {
                    if (arr[j] > key)
                        arr[j + 1] = arr[j];
                    else break;
                }
                arr[j + 1] = key;
            }
        }
  
        void QuickSort(int[] arr, int left, int right, int depth)
        {
            if (depth == 0)
            {
                int size = right - left + 1;
                if (size > 16)
                {
                    HeapSort(arr, left, right);
                }
                return;
            }
  
            int i = left, j = right;
            int pivot = arr[(left + right) / 2];
  
            do
            {
                while (arr[i] < pivot)
                    ++i;
                while (arr[j] > pivot)
                    --j;
                if (i <= j)
                {
                    Swap(ref arr[i], ref arr[j]);
                    ++i;
                    --j;
                }
            }
            while (i <= j);
  
            if (left < j)
                QuickSort(arr, left, j, depth - 1);
  
            if (i < right)
                QuickSort(arr, i, right, depth - 1);
  
        }
  
        public void IntroSort(int[] arr, int n)
        {
            int limit = Convert.ToInt32(2 * Math.Ceiling(Math.Log(n)));
            if (n <= 16)
            {
                InsertionSort(arr, 0, n - 1);
                return;
            }
            QuickSort(arr, 0, n - 1, limit);
            InsertionSort(arr, 0, n - 1);
        }
    }

참고

• [정렬] 인트로 정렬
• 인트로 정렬 | Wikipedia
• Introsort | Wikipedia
• 비교 정렬 | Wikipedia