notion ai가 설명합니다, 퀵정렬

TL;DR

퀵정렬은 분할정복의 예시 중 유명한 알고리즘으로, 병합정렬의 분할 후 정복 개념과는 달리 정복 후 분할 정책을 사용한다.
먼저 시퀀스를 두 부분으로 나누는 파티션 작업을 통해 피벗의 위치를 고정시킨다. 그리고 재귀호출을 사용하여 피벗의 왼쪽과 오른쪽에 대한 정렬을 각기 수행한다.
피벗의 위치는 맨앞, 맨뒤, 정 가운데, 랜덤, 중앙값으로 잡는 방법이 있고, 아래 수도코드는 랜덤으로 인덱스를 잡아 end로 보낸 뒤 파티셔닝을 수행한다.

Pseudo Code

유튜브 영상에서 보던 방식과는 조금 달라서 헤맸다. 실제 코드를 보면 two pointer개념을 사용하기는 하지만 pivot을 기점으로 물리적으로 분리된 공간에 실제로 데이터를 swap하는 것이 보였으나, 여기 방식에 따르면 일단 한쪽 끝 (아래 코드는 end)으로 피벗을 배치시킨 뒤에 pivot보다 작은 원소의 개수를 카운트 하고 incremental 하게 위치를 잡는 것을 볼 수 있다.

맨 마지막 줄이 중요한데, 피벗의 위치는 아직 끝이므로 본래 있어야 할 자리로 옮기는 것을 알 수 있다.

#include <random>
#include <utility>
static std::mt19937 engine{std::random_device{}()};
static std::uniform_int_distribution<unsigned int> generator{};

template <typename Iter, class Less>
Iter partition(Iter begin, Iter end, Less const &less) {
  auto pivot = begin + generator(engine) % (end - begin);
  std::swap(*pivot, *(end - 1));
  pivot = end - 1;
  size_t count = 0; // pivot보다 작은 원소의 개수를 카운트
  for (auto cur = begin; cur != pivot; ++cur) {
    if (less(*cur, *pivot)) {
      // move element to left
      std::swap(*cur, *(begin + count));
      count += 1;
    }
  }
  // move pivot to right place
  std::swap(*pivot, *(begin + count));
  return begin + count;
}

재귀호출 시 중요한 건 역시 종료조건이다. 나의 경우에는 end 가 STL의 이터레이터와 마찬가지로 미포함이기 때문에 범위가 비어있을 때 무조건 begin과 end 사이 1 차이가 난다.

partition을 마친 뒤에 리턴값인 피벗은 이미 확실하게 정렬이 되어있기 때문에 굳이 다음 이터레이션에 포함시킬 필요가 없다.

template <typename Iter, class Less>
void sort(Iter begin, Iter end, Less const &less) {
  if (end - begin <= 1) {
    return;
  }
  auto mid = partition(begin, end, less);
  sort(begin, mid, less);
  sort(mid + 1, end, less);
}

Testing

TEST(Test, 1) {
  vector<string> ls = {"hello", "my", "name", "is", "choi", "wheatley"};
  vector<string> ls2{ls};
  std::sort(ls.begin(), ls.end());
  sol1::sort(ls2.begin(), ls2.end(), std::less<string>{});
  ASSERT_EQ(ls, ls2);
}

확실히 nlogn 속도를 보여주기는 하지만 역시 하이브리드 방식의 표준정렬의 속도에 미치지는 못하는 것 같다.

constexpr size_t MAX_N = 200000;

TEST(Timeout, 1) {
  vector<int> ls;
  vector<int> ls2;
  std::generate_n(std::back_inserter(ls), MAX_N, std::bind(generator, engine));
  std::generate_n(std::back_inserter(ls2), MAX_N, std::bind(generator, engine));
  std::sort(ls.begin(), ls.end());
  sol1::sort(ls2.begin(), ls2.end(), std::less<int>{});
  ASSERT_EQ(ls, ls2);
}

notion ai가 설명합니다, 퀵정렬

관련 문제

TL;DR

Pseudo Code

Testing

관련 문제