[C++ STL] sort 구현하기
Joonas' Note
[C++ STL] sort 구현하기 본문
- 코드
저는 quick sort를 기반으로 구현했고, 그 중에서도 중간값이 아닌 (위치가) 중앙에 있는 값을 사용했습니다.
이 정도만 구현해도 많은 문제는 생기지 않았습니다.
다만 실제 std::sort 는 구조가 조금 다른 것으로 알고 있습니다. 크기가 100개 이하인 케이스는 insertion sort를 사용하는 등 최적화를 위해서 수정했다고 하네요.
template 함수로 작성했기 때문에, 타입은 별도로 명시하지 않아도 됩니다.
int형 배열 a[100]에 대해서도, std::sort 함수 쓰듯이 sort(a, a+100) 이라고 호출해도 동작합니다.
이전 게시글에서 구현한 vector를 파라미터로 넘겨도 동작합니다. 즉, sort(vec.begin(), vec.end()) 가능합니다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// based on quick sort | |
template<typename T> | |
void sort(T *arr, T *end) { | |
int l = 0, r = (end - arr) - 1; | |
if (l >= r) return; | |
T mid = arr[(l + r) / 2]; | |
while (l <= r) { | |
while (arr[l] < mid) ++l; | |
while (mid < arr[r]) --r; | |
if (l <= r) { | |
swap(arr[l++], arr[r--]); | |
} | |
} | |
sort(arr, arr + l); | |
sort(arr + l, end); | |
} |
'개발 > C++' 카테고리의 다른 글
[C++ STL] binary_search, upper_bound, lower_bound 구현하기 (0) | 2020.03.19 |
---|---|
Sublime Text 3에서 "프로시저 시작 지점" 오류 해결법 (0) | 2019.09.16 |
Chromium 빌드 (1) | 2019.05.07 |
C++ getline 공백 케이스 알아보기 (0) | 2018.11.25 |
MFC로 만든 미로 생성기 (0) | 2017.10.30 |