시소당

정렬 알고리즘 총 정리

관련  링크  -  Herong's  Tutorial  Notes  on  Sorting

다양한  정렬  알고리즘의  원리  및  자바로  구현한  소스,  성능  비교,  정렬  관련  자바  API  등이  잘  정리되어있습니다.

----------
덧붙임

혹시  참고가  되지  않을까해서  위에  소개된  몇  가지  정렬  알고리즘을  C++  로  구현해  봤습니다.

1.  선택  정렬
template  <typename  T>
void  SelectSort(T*  data,  int  size)
        {
        for  (int  i  =  0;  i  <  size;  ++i)
                {
                int  small  =  i;
                for  (int  j  =  i+1;  j  <  size;  ++j)
                        {
                        if  (data[j]  <  data[small])
                                small  =  j;
                        }
                std::swap(data[i],  data[small]);
                }
        }

2.  퀵  정렬
template  <typename  T>
int  Partial(T*  b,  int  size)
        {
        assert(size  >  1);
        int  last  =  size-1,  big  =  -1;
        for  (int  i  =  0;  i  <  last;  ++i)
                {
                if  (b[last]  >  b[i])
                        std::swap(b[i],  b[++big]);
                }
        std::swap(b[last],  b[++big]);
        return  big;
        }

template  <typename  T>
void  QSort(T*  b,  int  size)
        {
        if  (size  <=  1)
                return;
        int  mid  =  Partial(b,  size);
        QSort(b,  mid);
        QSort(b+mid+1,  size-mid-1);
        }

3.  힙  정렬
inline  int  Left(int  idx)  {  return  (idx+1)*2  -  1;  }
inline  int  Right(int  idx)  {  return  (idx+1)*2;  }
inline  bool  IsLeaf(int  idx,  int  size)  {  return  idx  >=  (size/2);  }

template  <typename  T>
void  Heapify(T*  data,  int  size,  int  idx)
        {
        assert(idx  <  size);
        int  left  =  Left(idx),  right  =  Right(idx);
        int  biggest  =  idx;
        if  (left  <  size  &&  data[left]  >  data[biggest])
                biggest  =  left;
        if  (right  <  size  &&  data[right]  >  data[biggest])
                biggest  =  right;
        if  (biggest  !=  idx)
                {
                std::swap(data[idx],  data[biggest]);
                Heapify(data,  size,  biggest);
                }
        }

template  <typename  T>
void  MakeHeap(T*  data,  int  size)
        {
        for  (int  idx  =  size/2  -  1;  idx  >=  0;  --idx)
                Heapify(data,  size,  idx);
        }

template  <typename  T>
void  HeapSort(T*  data,  int  size)
        {
        MakeHeap(data,  size);
        for  (int  i  =  size-1;  i  >  0;  --i)
                {
                std::swap(data[0],  data[i]);
                Heapify(data,  i,  0);
                }
        }

출처  :  http://agbird.egloos.com/3388944