정렬 알고리즘은 변경 알고리즘의 특수한 형태이다. 정렬 알고리즘에는 힙 관련 알고리즘이 있는데 힙 자료구조를 간단한게 설명하면 항상 트리 내의 모든 원소가 부모 노드보다 큰 값(혹은 작은 값)을 갖는 완전 이진 트리이다.그래서 루트 노드는항상 가장 작은 값(혹은 가장 큰 값)을 가진다.

make_heap(b,e)

make_heap(b,e) 알고리즘은 구간 [b,e)의 순차열을 힘 구조롤 만든다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(60);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	make_heap(v.begin(), v.end());
	cout << "v[힙생성] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

결과에 있는 힙 생성 후 v를 그림으로 나타내보겠다.

루트 노드가 가장 크고 부모 노드는 자식 노드 보다 큰 것을 볼 수 있다.

push_heap(b,e)

push_heap(b,e) 알고리즘은 구간 [b,e)의 힙에 원소를 추가하는 알고리즘이다. push_heap() 알고리즘은 일반적으로 멤버함수 push_back()과 함께 사용된다. push_heap(b,e)은 구간 [b,e)의 가장 마지막 원소를 부모 노드와 비교해사며 힙 연산을 수행하기 때문이다. 예시를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(60);

	make_heap(v.begin(), v.end());
	cout << "v[힙생성] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	v.push_back(35);
	cout << "v 순차열에 35 추가 : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	push_heap(v.begin(), v.end());
	cout << "v[힙 추가] 연산 수행 : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

pop_heap(b,e)

pop_heap(b,e) 알고리즘은 힙에서 루트 노드를 제거한다. pop_heap(b,e)는 구간 [b,e)의 첫 원소를 가장 끝 원소와 교환한 후 힙이 유지되게 연산을 한다. 예시를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(60);

	make_heap(v.begin(), v.end());
	cout << "v[힙 생성] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	pop_heap(v.begin(),v.end());
	cout << "v[힙 제거] 연산 수행 : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}

루트 노드 였던 60이 마지막 원소가 되고, 10이 루트가 되지 않는 이유는 다시 힙 구조로 만들기 위해 자동으로 정렬하기 때문이다.

sort_heap(b,e)

sort_heap(b,e) 알고리즘은 힙을 정렬 할 때 사용한다. 힙 연산을 통해 정렬을 수행한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(60);

	make_heap(v.begin(), v.end());
	cout << "v[힙 생성] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	cout << "v[힙 정렬] : ";
	sort_heap(v.begin(), v.end());
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

당연한거지만 힙 관련 알고리즘은 힙 자료구조에만 동작한다.

조건자 버전 힙 알고리즘

make_heap(b,e,f) / push_heap(b,e,f) / pop_heap(b,e,f) / sort_heap(b,e,f) 모두 조건자 버전 힙 알고리즘으로 조건자 f를 사용한다. 예시를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(40);
	v.push_back(10);
	v.push_back(50);
	v.push_back(30);
	v.push_back(20);
	v.push_back(60);

	// 부모 노드가 모든 자식 노드보다 작은 힙 생성
	make_heap(v.begin(), v.end(),greater<int>());
	cout << "v[힙 생성] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	v.push_back(35);
	push_heap(v.begin(), v.end(), greater<int>());
	cout << "v[힙 추가] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	sort_heap(v.begin(), v.end(),greater<int>());
	cout << "v[힙 정렬] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

nth_element()

순차열의 원소 중 n개의 원소를 선별하고자 할 때 사용한다. nth_element(b,m,e)는 구간 [b,e)의 원소 중 m-b개 만큼의 원소를 선별하여 (사전순) [b,m)의 순차열에 넣는다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	
	for (int i = 0; i < 100; i++) {
		v.push_back(rand() % 1000);
	}

	nth_element(v.begin(), v.begin() + 20, v.end());

	cout << "v[상위 20게] ";
	for (vector<int>::size_type i = 0; i < 20; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << "v[상위 20게] ";
	for (vector<int>::size_type i = 20; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

단순히 0~999개의 랜점 정수 100개를 컨테이너 v에 저장하고 상위 20개 원소를 선별한 것이다.

순차열 정렬 알고리즘들

순차열을 정렬하고 싶을 때는 sort() / stable_sort() / partial_sort()를 사용한다, 각각의 특딩을 살펴보자

sort() : 퀵정렬 기반

stable_sort() : 머지정렬 기반

partial_sort() : 힙정렬 기반

각 알고리즘들의 예시를 보자

sort()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	
	for (int i = 0; i < 100; i++) {
		v.push_back(rand() % 1000);
	}

	cout << "v [정렬 전] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << endl;

	sort(v.begin(), v.end());
	cout << "v [정렬 less] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << endl;

	sort(v.begin(), v.end(), greater<int>());
	cout << "v [정렬 greater] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

stable_sort()

원소의 상대적인 위치는 지키며 정렬하고 싶을 때 사용한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(30);
	v.push_back(50);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(10);
	v.push_back(40);

	cout << "v [정렬 전] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << endl;

	stable_sort(v.begin(), v.end());
	cout << "v [정렬 less] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << endl;

	stable_sort(v.begin(), v.end(), greater<int>());
	cout << "v [정렬 greater] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

partial_sort()

순차열의 상위 구간만 정렬하거나 힙정렬의 특징이 필요할 때 사용한다. partial_sort(b,m,e)는 구간 [b,e)의 원소를 [b,m)의 순차열에 원소를 정렬한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	for (int i = 0; i < 100; i++) {
		v.push_back(rand() % 1000);
	}

	partial_sort(v.begin(), v.begin() + 20, v.end());

	cout << "v [상위 정렬 20개] : ";
	for (vector<int>::size_type i = 0; i <20; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << endl;

	cout << "v [하위 80개] : ";
	for (vector<int>::size_type i = 20; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << endl;
}

결과에서 알 수 있듯이 v의 원소 중 작은 것 들 20개를 골라서 정렬한 모습이다.

partial_sort_copy()

순차열의 상위 구간만 정렬하여 목적지 순차열로 복사하려면 partial_sort-copy() 알고리즘을 사용한다.

partial_sort_copy(b,e,b2,e2)는 구간 [b,e)의 원소중 e2-b2개의 상위 구간만을 정렬하여 [b2,e2)의 순차열로 복사한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;

	for (int i = 0; i < 100; i++) {
		v1.push_back(rand() % 1000);
	}

	cout << "v1 [정렬 전] : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;
	cout << endl;

	vector<int> v2(20);

	partial_sort_copy(v1.begin(), v1.end(), v2.begin(), v2.end());

	cout << "v2 [less] : ";
	for (vector<int>::size_type i = 0; i <v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
	cout << endl;

	partial_sort_copy(v1.begin(), v1.end(), v2.begin(), v2.end(),greater<int>());

	cout << "v2 [greater] : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
	cout << endl;
}

[STL] 정렬 알고리즘

make_heap(b,e)

push_heap(b,e)

pop_heap(b,e)

sort_heap(b,e)

조건자 버전 힙 알고리즘

nth_element()

순차열 정렬 알고리즘들

sort()

stable_sort()

partial_sort()

partial_sort_copy()

KSC

make_heap(b,e)

push_heap(b,e)

pop_heap(b,e)

sort_heap(b,e)

조건자 버전 힙 알고리즘

nth_element()

순차열 정렬 알고리즘들

sort()

stable_sort()

partial_sort()

partial_sort_copy()

Share this post