2751 수 정렬하기 2

STL에서 제공하는 sort 함수는 템플릿 기반으로 quick sort를 수행한다.

quick sort는 다른 정렬들에 비해 nlogn의 수행속도를 가지는데, 분할 정복이라는 방법을 사용하기 때문이다.

예를 들어, 버블 정렬과 비교해보면 버블 정렬은 n^2의 시간복잡도를 가지는 반면, quick sort는 pivot을 기준으로 탐색 범위를 절반으로 줄여가기 때문에 nlogn의 시간복잡도를 가질 수 있다.

참고 : gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int main()
{
	cin >> N;
	vector<int> v(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	for (const auto& item : v) {
		printf("%d\n", item);
	}
	return 0;
}