[기초] 정렬(sort) 알고리즘

 

 

정렬

정렬은 어떤 자료를 순서대로 배열하는 것을 의미합니다.

 

 

많은 알고리즘 문제에서 정렬을 사용하여 문제를 해결합니다.

 

정렬은 직접 구현하기 보다는 STL에 있는 sort를 사용하는 것이 좋습니다.

(STL sort는 intro sort를 사용한다고 합니다. 매우 빠름)

 

 

 

참고 링크

 

https://www.acmicpc.net/board/view/16770

글 읽기 - stl의 sort 로는 시간초과가뜨는데 제가 틀린건가요?

 

 

Introsort - Wikipedia

---

 

정렬 알고리즘에는 여러가지가 있는데, 크게

 

 O(N^2) 정렬 알고리즘과 O(N log N) 정렬 알고리즘이 있습니다.

 

정렬은 빠르면 빠를 수록 좋기 때문에 O(N log N) 정렬 알고리즘을 주로 사용합니다.

 

 

- O(N^2) 정렬 알고리즘 -

선택 정렬, 버블 정렬, 삽입 정렬 등

 

- O(N log N) 정렬 알고리즘 -

퀵 정렬, 힙 정렬, 병합 정렬 등

 

C++ 에서 sort()는 algorithm 헤더를 include하면 쓸 수 있습니다.

 

 

//a[0] 부터 a[n-1]까지를 정렬하는 소스
int n = 10;
int a[10] = {};
sort(a, a+n);

//vector를 정렬하는 소스
vector<int> a;
sort(a.begin(), a.end());

 

 

 

---

 

백준 좌표 정렬하기

 

x, y좌표가 여러 개 있을 때, x가 증가하는 순으로, 같으면 y가 증가하는 순서로 정렬하는 문제

 

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

 

위 문제는 기본 자료형을 정렬하는 것이 아니라 구조체를 정렬하는 것이기 때문에

 

 이런 구조체나 클래스를 정렬하는 문제는 pair를 사용하면 편하게 풀 수 있습니다.

 

int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) {
	cin >> a[i].first >> a[i].second;
}
sort(a.begin(), a.end());
for (int i = 0; i < a.size(); i++) {
	cout << a[i].first << a[i].second << endl;
}

 

 

직접 struct를 구현하는 경우에는 비교 함수를 만들어 줘야 합니다.

struct Point {
	int x, y;
};

// cmp함수는 u가 v의 앞에 오는 것이면 true, 아니면 flase, const 와 &는 붙여야 한다.
bool cmp(const Point &u, const Point &v) { 
	if (u.x < v.x) {
    	return true;
    }
    else if (u.x == v.x) {
    	return u.y < v.y;
    }
    else {
    	return false;
    }
}

//위와 같이 비교함수를 만들 경우 3번째 인자로 함수 이름을 넘겨줘야 한다.
sort(a.begin(), a.end(), cmp);

 

 

< 연산자를 over loading 할 수도 있습니다.

//이 경우에는 3번째 인자가 필요 없다.

struct Point {
	int x, y;
    bool operator < (const Point &v) const {
    	if (x <v.x) {
        	return true;
        }
        else if (x == v.x) {
        	return y < v.y;
        }
        else {
        	return flase;
        }
    }
}

 

+버블 정렬은 입력의 형태와 상관없이 언제나 같은 횟수의 비교를 수행한다.