[C++ STL] sort 구현하기

Joonas' Note

[C++ STL] sort 구현하기 본문

개발/C++

[C++ STL] sort 구현하기

2020. 3. 19. 17:26 joonas 읽는데 1분
  • 코드

저는 quick sort를 기반으로 구현했고, 그 중에서도 중간값이 아닌 (위치가) 중앙에 있는 값을 사용했습니다.

이 정도만 구현해도 많은 문제는 생기지 않았습니다.


다만 실제 std::sort 는 구조가 조금 다른 것으로 알고 있습니다. 크기가 100개 이하인 케이스는 insertion sort를 사용하는 등 최적화를 위해서 수정했다고 하네요. 


template 함수로 작성했기 때문에, 타입은 별도로 명시하지 않아도 됩니다.

int형 배열 a[100]에 대해서도, std::sort 함수 쓰듯이 sort(a, a+100) 이라고 호출해도 동작합니다.


이전 게시글에서 구현한 vector를 파라미터로 넘겨도 동작합니다. 즉, sort(vec.begin(), vec.end()) 가능합니다.

코드

// 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);
}
view raw sort.cpp hosted with ❤ by GitHub

Comments