9. 정렬 관련 알고리즘(sort, binary_search, merge)

sort

---

sort는 컨테이너에 있는 데이터들을 내림차순 또는 오름차순으로 정렬 할 때 가장 자주 사용하는 알고리즘이다. 컨테이너에 저장하는 데이터의자료 형이 기본형이라면 STL에 있는 greate나 less 비교 조건자를 사용한다.(STL의 string의 정렬에도 사용할 수 있다. 다만 이때는 알파벳 순서로 정렬된다). 기본형이 아닌 경우에는 직접 비교 조건자를 만들어서 사용해야 한다.

 

 

<less와 greater 비교 조건자를 사용한 sort>

 

 

 

<USER 구조체의 Money를 기준으로 정렬>

 

 

 

 

binary_search

---

이미 정렬 되어 있는 것 중에서 특정 데이터가 지정한 구간에 있는지 조사하는 알고리즘이다. 이것도 sort와 같이 비교 조건자가 필요 없는 버전과 필요한 번전 두 개가 있다(단 sort와 다르게 랜덤 접근 반복자가 없는 컨테이너도 사용할 수 있다).

 

binary_search 를 사용할 때는 꼭 먼저 정렬해야 한다는 것을 잊지 말아야 한다.

 

 

 

<정렬 후 binary_search 사용>

 

 

 

 

merge

---

두 개의 정렬된 구간을 합칠 때 사용하는 것으로 두 구간과 겹치지 않은 곳에 합친 결과를 넣어야 한다. 주의해야 할 점은 합치기 전에 이미 정렬이 되어 있어야 하며 합친 결과를 넣는 것은 합치는 것들과 겹치면 안되며, 또한 합친 결과를 넣을 수 있는 공간을 확보하고 있어야 한다.

 

 

 

 

<두 개의 vector의 merge >

 

 

 

출처 : Thinking About C++ STL 프로그래밍 (최홍배 지음)