[C++] 정렬

 

본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다.

 

정렬은 기본적인 알고리즘 설계 문제이다.

 

다양한 효율적인 알고리즘은 서브루틴으로서 정렬을 채택한다.

왜냐하면 요소들이 정렬되어 있다면, 데이터를 다루기 쉬워지기 때문이다.

 

효율적인 일반 알고리즘은 O(nlogn)시간에서 작동한다.

 

O(n^2) 알고리즘

대표적인 O(n^2) 정렬 알고리즘은 "버블 정렬"이다.

버블 정렬은 n라운드로 구성되며, 각 라운드마다 알고리즘을 반복한다.

 

1. 두 연속 원소가 올바른 정렬이 아닐 시, 순서를 바꾼다.

for(int i=0; i<n; i++) {
	for(int j = 0; j<n-1; j++) {
		if(array[j] > array[j+1]) {
			swap(array[j], array[j+1]);
		}
	}
}

 

버블 정렬은 항상 연속된 두 원소의 위치를 바꾸는 알고리즘이다. 이는 최악의 경우, O(n^2) 이상의 시간 복잡도를 요구한다. 

 

O(nlogn) 알고리즘

재귀를 통한 "병합 정렬"을 통해 효율적인 O(nlogn) 정렬이 가능하다.

병합 정렬은 다음과 같이 하위 배열[a~b]를 정렬한다.

1.  If a=b, 하위 배열이 정렬되어 있으므로 아무 것도 하지 않는다.
2.  중간 원소의 위치를 계산한다. : k = [(a+b)/2]
3.  첫번째 하위 배열[a~k]을 재귀적으로 정렬한다.
4.  두번째 하위 배열[k+1~b]을 재귀적으로 정렬한다.
5.  두 하위 배열을 합친다.

병합 정렬은 하위 배열의 사이즈를 반으로 줄이기 때문에 효율적이다.

재귀는 O(logn)으로 구성되며, 각 단계는 O(n) 시간을 사용한다.

 

C++ 정렬

C++ 표준 라이브러리는 이미 배열 및 데이터 구조 정렬을 위한 정렬 함수를 포함하고 있다.

 

1. sorts a vector : 오름차순

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

// result : {2,3,3,4,5,5,8} 

 2. sorts a vector : 내림차순

sort(v.rbegin(), v.rend());

3. 일반적인 배열 정렬

int n = 7;
int a[] = {4,2,5,3,5,8,3};
sort(a, a+n);

4. string 정렬

string 정렬은 문자의 순서대로 정렬하는 것을 의미한다.

string s = "monkey";
sort(s.begin(), s.end());

// result : "ekmnoy"