2007년 02월 20일

Quick Sort 구현

/* DO NOT reproduce the code above without any permission.      */
/* Contact me via email(ted78kr at yahoo.co.kr) if you wish to. */

#include <iostream>

using namespace std;

class SortUtil {
public:
    static void quick_sort(int* begin, int* end);
    static void disp_array(const int* begin, const int* end);
};

int main(int argc, char* argv[])
{
    int a[] = {1, 28, 38, 11, 16, 8, 20, 12, 24, 19, 13, 45, 17};

    SortUtil::quick_sort(&a[0], &a[sizeof(a)/sizeof(int)]);
  
    SortUtil::disp_array(&a[0], &a[sizeof(a)/sizeof(int)]);

    return 0;
}

void SortUtil::disp_array(const int* begin, const int* end)
{
    for(const int* iter = begin; iter < end; ++iter) {
        cout << *iter << ' ';
    }

    cout << endl;
}

void SortUtil::quick_sort(int* begin, int* end)
{
    if((end - begin) <= 1) {
        return;
    }

    int* pivot = end - 1;
    int* s_idx = begin;
    int* e_idx = end - 2;
  
    while(true) {
        while(*e_idx > *pivot) --e_idx;
        while(*s_idx < *pivot) ++s_idx;
      
        if(e_idx <= s_idx) {
            break;
        }
      
        swap(*s_idx, *e_idx);
    }

    swap(*s_idx, *pivot);
    quick_sort(begin, s_idx);
    quick_sort(s_idx + 1, end);
}

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

by 행궈 | 2007/02/20 23:56 | C/C++ | 트랙백

트랙백 주소 : http://ted78.egloos.com/tb/3124529
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
※ 로그인 사용자만 덧글을 남길 수 있습니다.

◀ 이전 페이지          다음 페이지 ▶