본문 바로가기

프로그래밍

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);

    }

}


  • slowdk 2014.01.17 02:11 댓글주소 수정/삭제 댓글쓰기

    알고리즘 초보인데, 퀵소팅 코드를 보면서 궁금한게 있어 질문 드리려고 합니다.

    partition함수에서 std:swap을 2번 사용 하셨는데요 (for문 돌기 전 1번, 돌고나서 1번) 이 두 구문이 있는 이유가 잘 이해가 안가서요.

    괜찮으시다면 알려주실 수 있나요?

    • 안녕하세요?
      첫번째 스왑은 피벗에 있는 값을 맨 오른쪽 값과 바꾸는용도입니다.
      피벗 값을 그 위치에 두고 하려면 스왑이 더 많이 필요할수도 있기때문에 그냥 애초부터 맨 오른쪽에다가 옴겨두는거죠.
      그리고 루프를 마치고나면,
      [피벗보다작은값들][피벗과같거나큰값들][피벗] 순서로 정렬이됩니다. 그리고 storeIndex는 [피벗과같거나큰값들]중 첫번째를 가르키고 있게 됩니다.
      그러므로 [피벗보다작은값들][피벗][피벗과같거나큰값들] 형태로 만들어주기 위해서 가장 오른쪽 값(피벗)과 storeIndex의 값을 swap 해주면됩니다.