[정렬] Part. 2

!·2022년 8월 6일
0

자료구조&알고리즘

목록 보기
10/10

Counting Sort

  • 정렬하고자 하는 배열의 빈도수를 저장하는 배열을 통해 배열을 하는 방법.

Counting Sort의 시간복잡도

  • 정렬하고자 하는 배열의 크기가 N이고, 수의 범위가 K라고 할 떄, 시간복잡도는 O(N+K) 이다.
  • 수의 범위가 적을때는 매우 유리한 정렬방법이다.

코드

#include <iostream>
using namespace std;

int n;
int freq[2000001];
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0;i<n;i++)
    {
        int a;
        cin >> a;
        freq[1000000+a]++;
    }
    for(int i = 0;i<2000001;i++)
    {
        while(freq[i]--)
            cout << i-1000000 << '\n';
    }
}

Radix Sort

  • 각 자리수를 기준으로 정렬하는 방법.
  • 처음 1의 자리의 수를 기준으로 자리수 배열 에 넣는다.
  • 그 다음, 그 정렬된 수들을 다시 10의 자리의 수를 기준으로 자리수 배열에 넣는다. 이 과정을 최대 자리수까지 반복한다.

Radix Sort의 시간복잡도

원소의 자리수의 최대 개수가 D이면, D번의 걸쳐서 정렬을 진행한다. 이때 만약 리스트의 개수가 K개 일 때, 엄밀히 말하면 시간복잡도는 O(D(N+K)) 이다. 하지만 K는 일반적으로 매우 작아 무시가 가능하므로. O(DN) 이라고 할 수 있다.


코드

#include <bits/stdc++.h>
using namespace std;

int n = 15;
int arr[1000001] = {12, 421, 46, 674, 103, 502, 7, 100, 21, 545, 722, 227, 62, 91, 240};

// 1, 10, 100의 자리에 대해서 진행, 수가 최대 3자리수가 아닐 경우 d를 조절해야 함
int d = 3;
// p10[i] = 10의 i승
int p10[3];

// x의 10^a 자리의 값을 반환하는 함수
int digitNum(int x, int a){
  return (x / p10[a]) % 10;
}

vector<int> l[10];
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  p10[0] = 1;
  for(int i = 1; i < d; i++) p10[i] = p10[i-1] * 10;
  
  for(int i = 0; i < d; i++){
    for(int j = 0; j < 10; j++) l[j].clear();
    // 각 수를 list에 대입
    for(int j = 0; j < n; j++)
      l[digitNum(arr[j], i)].push_back(arr[j]);
    // 0번 리스트부터 차례로 다시 arr에 넣어 재배열
    int aidx = 0;
    for(int j = 0; j < 10; j++){
      for(auto x : l[j]) arr[aidx++] = x;
    }
  }
  for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}

STL sort()

c++에서 기본적으로 제공하는 STL sort() 함수는 퀵 정렬을 기반으로 구현되어 있다. 또한, 퀵 정렬의 경우 최악의 경우 O(N^2)의 시간복잡도를 가지지만, STL sort() 의 경우 재귀의 깊이가 너무 깊어지게 되면 O(NlogN) 이 보장되는 정렬알고리즘으로 정렬을 진행하기 떄문에 O(NlogN) 의 시간복잡도가 보장된다. 하지만, sort() 함수는 stable 정렬이 아니기때문에 주의할 필요가 있다. 이를 위해서는 stable_sort() 를 이용하면 된다.

STL에서 제공되는 Pair, Tuple 컨테이너 모두, 앞의 원소부터 먼저 비교를 진행하기때문에 편하게 사용하면 된다.

int a[5] = {2,6,1,3,7};
sort(a,a+5);

vector<int> v = {1,4,5,2,7};
sort(v.begin(), v.end());

또한 sort() 함수의 장점은 비교함수를 사용자가 직접 정의할 수 있다는 점이다.

int a[5] = {2,6,1,3,7};

bool cmp(int a, int b)
{
	return b > a
}
sort(a,a+5,cmp);

위의 코드는 오름차순으로 정렬을 수행하는 경우이다. 사용자가 함수를 직접 정의하는 경우에는 원소가 같은 경우에 true 를 반환하면 절대 안된다. 런타임 오류가 발생할 가능성이 있다.
또한, 단순히 오름차순, 내림차순 정렬이 아닌 새로운 정의에 따라 sort()를 수행하도록 할 수 있다.

int a[5] = {2,6,1,3,7};

bool cmp(int a, int b)
{
	if(a%5 != b%5) return a%5 < b%5
    return a < b
}
sort(a,a+5,cmp);

위의 코드는 5로 나눈 나머지순으로, 5로 나눈 나머지가 같다면 크기순으로 정렬을 하는 경우이다.

또한 비교함수의 인자로 STL 객체나, 클래스 객체를 전달시 reference를 사용하는 것이 좋다.

bool cmp(string a, string b)
{
	return a.back() < b.back()
}
// 아래 코드가 더 낫다.
bool cmp(string& a, string& b)
{
	return a.back() < b.back()
}

불필요한 값의 복사를 줄여 시간을 약간 절약할 수 있다.

profile
개발자 지망생

0개의 댓글