partition, nth_element, partitial_sort, sort

[[[원리 분석]]]

partition: partition을 이용하여 길이가 1인 문자열과 나머지 문자열을 분리하라.

이제는 이것만 보고도 어떻게 사용하는 함수인지 바로 예측 가능해야 한다.

회사에서도 이런식으로 자신들의 함수를 정의한 메뉴얼을 만들어서 건네줄텐데 우리는 그것을 사용할 줄 알아야 한다.

시작 주소, 끝 주소, 조건자

함수구현은 안하겠다. 사용 방법만 알아보자.

 

==헤더 파일==

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#include <random>

#include <numeric>

 

==소스 코드==

https://koreatopclass.tistory.com/20 << 참고

1. 정렬되어 있지 않아도 분리할 수 있다는 것을 알려주기 위해 shuffle 함수를 사용하였다.

https://koreatopclass.tistory.com/21 << 참고

2. 위에 원리 분석에 써놓은 대로 시작, 끝, 조건자를 넣었다.

3. 결과값으로 분리가 끝난 위치의 다음 주소를 반환한다(p라고 하겠다)

4. 따라서 first ~ p -1 까지가 길이가 1인 문자열이 정렬되고 p ~ last 까지가 나머지 문자열이 정렬된다.

5. 순서대로 정렬하지는 않는다. 1 2 3 4 5가 2 4 3 5 1로 저장되었다.

6. 복잡도가 정렬에 비해서 현저하게 낮다.

7. 성적에 따라 나누는 예시를 생각해 볼 수 있다.

 

nth_element: 30등까지 순서 없이 정렬

==소스 코드==

first부터 nth까지 값을 채워는데 1 ~ 30의 숫자면 되고 순서는 안지켜도 된다

1. 30등까지 정렬이 되긴 했지만 순차 정렬은 아니다.

2. nth_element 함수는 return값이 없다.

3. v.begin부터 nth까지에 값이 들어갈텐데 위 코드에 따르면 1 ~30까지의 값들이 들어간다.

 

partitial_sort: 30등까지 순차 정렬

부분 정렬. 말 그대로 어느 부분 까지만 정렬하는 함

nth_element에서 이 부분만 수정

얘도 리턴값 없다.

정말로 30까지만 정렬한 것을 볼 수 있다.

first부터 nth까지 값을 순서대로 채워라!!

 

sort: 정렬에 관해 공부하는 김에 sort함수도 다시 한번 복습. 전체 정렬 함수

rbegin을 사용한 역정렬, 필터를 사용한 역정렬, 필터를 사용한 출력 제한, 조건자 변경을 통한 내멋대로 정렬

list함수의 멤버 sort  등 말할 주제가 너무 많음.

rbegin에 관한 예제를 적고 나면 rbegin 반복자 함수 구현 해보는 예제도 만들어야 하고...

sort 함수에 대해서 적고 싶은게 많은데 기회 되면 하도록 하겠다.

 

==왜 이렇게 많이 나눠놨을까?==

소 잡는 칼로 닭 잡지 마라.

내가 필요한 목적에 따라 골라서 사용하라. 

귤 농사 짓는데 불량, 정상 나누기 위해 partition 

무게 얼마 이상은 여기, 저기 나눌 때 sort할 필요가 전혀 없다.

용도에 맞는 코딩을 하자.

게임에서는 무거운 코드를 사용했다가 괜히 프레임이 떨어질 수 있다.

 

학습 장소: 한국공학대학교 게임공학과 수업

참고: https://en.cppreference.com/w/