5일차 강의 (14 ~ 15강)

정렬I (14강)

*max_element(arr, arr+k) → arr[0], arr[1], ..., arr[k-1]에서 최댓값인 원소의 주소를 반환(+참조)

선택정렬, 버블정렬, 삽입정렬 O(N^2)

 

Merge Sort O(NlogN)

 

Stable Sort

우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬

 

Quick Sort O(NlogN)

- 코딩테스트에서 STL을 못 쓰게 하고 직접 구현해서 정렬을 사용해야 한다면 Quick Sort 구현하지말고 다른 방식으로 

 퀵소트의 장점은 추가적인 공간이 필요하지 않다는 점, cache hit rate가 높아서 속도가 빠름

→ 추가적인 공간을 사용하지 않고(In-Place Sort) pivot을 제자리로 보내는 방법 필요, stable sort가 아

- 단점 : 퀵소트는 평균적으로 O(NlogN)이지만 최악의경우 O(n^2)

 

정렬II (15강)

Counting Sort

각 수의 등장 횟수를 저장해야 함

수의 범위가 어느정도 한정적일 때에만 사용 가능 (대략 1000만이하)

 

Radix Sort (기수정렬)

자릿수를 이용해서 정렬을 수행하는 알고리즘, 카운팅소트를 응용

코딩테스트때 직접 구현을 해야하는 상황은 없을 것 (개념 이해만 하고 넘어가기)

정수의 거듭제곱을 계산할 땐 오차가 발생할 수 있으므로 되도록 반복문으로 계산하는 것이 좋음

 

Comparison Sort

버블 소트

머지 소트

퀵 소트

 

Non-comparison Sort

카운팅 소트

라딕스 소트

 

코딩 테스트에서는 stl의 sort함수 사용 → 최악의 경우에도 O(NlogN) 보장

기본적으로 stable sort는 아님.

만약 stable sort가 꼭 필요한 경우 stable_sort 사용

pair와 tuple은 앞부터 우선으로 비교하도록 이미 정해져 있음.

 

bool cmp를 만들어서 직접 비교방식을 선택할 수 있음

 

주의사항

- 비교함수는 두 값이 같을 때(혹은 우선순위가 같을 때) false를 반환

- 비교함수의 인자로 stl 혹은 클래스 객체를 전달 시 reference를 사용 (string& a, string& b)