챕터5-1. 정렬 | 기초

# 정렬 알고리즘

- 시간복잡도에 따라 크게 2가지로 나눌 수 있다.
- 실제 사용하게 되는 것은 효율이 좋은 O(NlogN) 알고리즘임.

1. 시간 복잡도가 O(N^2)인 알고리즘
- 선택, 버블, 삽입 정렬

2. 시간 복잡도가 O(NlogN)인 알고리즘
- 퀵, 힙, 병합 정렬

 

# 언어별 정렬함수

- 정렬 알고리즘을 직접 구현하는 것 보다는, 효율적으로 구현된 내장 함수를 사용하는 것이 더 좋다.

 

@ C++의 경우
- STL인 <algorithm> 헤더의 sort() 사용, sort(begin, end) 는 begin부터 end전까지 정렬해줌

begin은 첫번째 원소를 가리키고, end는 마지막 원소 다음을 가리킨다.

// 배열을 정렬하는 소스
int a[10] = {};
sort(a, a+10); // a배열에서 index 0 ~ 10-1 구간을 정렬한다.

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

@ Java의 경우
- Arrays.sort(), Collections.sort()

@ Python의 경우

- sort()