std::vector 정렬하기 - quick sort, merge sort

std::vector를 정렬하기 위해서는 std::sort를 쓰면 되지만, 요즘 인터뷰관련해서 학부때 공부했던걸 복습하고 있던 참에, 그새 소팅을 까먹은걸 깨닫고 다시 공부해서 작성해 보았습니다.

array가 아니라 vector 버전으로 짰습니다. array버전은 많지만 vector 버전은 별로 없는것 같아 학생분들이나 인터뷰보실분들이 필요할것 같아서 공유합니다. 물론 array나 vector나 마찬가지지이긴 하지만, vector쪽이 코드가 더 간결해집니다.

<퀵 소트>

template <typename T>

void quick_sort_recursive(std::vector<T>& v, size_t left, size_t right) {

    size_t i = left, j = right;

    T pivot = v[(left+right)/2];

    // partition

    while(i <= j) {

        while(v[i] < pivot)

            i++;

        while(v[j] > pivot)

            j--;

        if(i <= j) {

            std::swap(v[i++], v[j--]);

        }

    }

 // recursive call

    if(left < j)

        quick_sort_recursive(v, left, j);

    if(i < right)

        quick_sort_recursive(v, i, right);

}

template <typename T>

void quicksort(std::vector<T>& array) {

    quicksort_recursive(array, 0, array.size()-1);

}

<머지소트>

template <typename T>

void merge(std::vector<T>& t, std::vector<T>& a1, std::vector<T>& a2) {

    t.clear();

    typename std::vector<T>::iterator itr1 = a1.begin();

    typename std::vector<T>::iterator itr2 = a2.begin();

    while(itr1 != a1.end() || itr2 != a2.end()) {

        if(itr1 != a1.end() && itr2 != a2.end()) {

            if(*itr1 < *itr2) {

                t.push_back(*itr1++);

            } else {

                t.push_back(*itr2++);

            }

        } else {

            if(itr1 != a1.end()) {

                t.push_back(*itr1++);

            } else {

                t.push_back(*itr2++);

            }

        }

    }

}

template <typename T>

void merge_sort(std::vector<T>& array) {

    if(1 < array.size()) {

        int f = array.size() / 2;

        std::vector<T> array1(array.begin(), array.begin() + f);

        merge_sort(array1);

        std::vector<T> array2(array.begin()+f, array.end());

        merge_sort(array2);

        merge(array, array1, array2);

    }

}