정렬 2

정렬 2

Counting Sort

• 수를 세고 난 뒤 정렬
• 수의 범위가 한정적일 경우 사용 가능
• Non-Comparison Sort

  Radix Sort

• 기수 정렬
• 자릿수를 이용하여 정렬을 수행하고 counting sort를 응용한 알고리즘이라고도 생각할 수 있음
• 1의 자리부터 각 자리별로 정렬 하고 재배열
• 시간복잡도: O(DN) D: 자릿수의 최대 개수
• Non-Comparison Sort

  STL Sort

• STL Sort는 stable sort가 아님.

  주의 사항

• 비교 함수는 두 값이 같을 때(혹은 우선순위가 같을 때) false를 반환

  // 잘못된 경우
  bool wrongcomp(int a,int b){
    if(a>=b){
        return true;
    }
    else{
        return false;
    }
  }
  bool comp(int a,int b){
    return a>b;
  }
  

• 비교 함수의 인자로 STL 혹은 클래스 객체를 전달시 reference를 사용

  bool badcmp(string a,string b){
    return a.back() < b.back(); 
  }
  bool cmp(const string& a,const string& b){
    return a.back() < b.back();
  }