칵테일 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

칵테일 정렬(cocktail sort)은 양방향 거품 정렬(bidirectional bubble sort) 또는 셰이커 정렬(shaker sort) 등으로도 불리는 거품 정렬의 변형이다. 거품 정렬과는 달리 매 라운드마다 리스트의 순서를 바꾼다.

소스 코드[편집]

C++[편집]

templatetypename BidirectionalIterator〉
void cocktailShaker(BidirectionalIterator first, BidirectionalIterator last)
{
    BidirectionalIterator shift = first;
    BidirectionalIterator i;
 
    while (first < last) {
        i = first;
        while (++i < last) {        // [shift, last)
            if (*i < *(i-1)) {
                std::iter_swap(i, i-1);
                shift = i;
            }
        }
        last = shift;
 
        i = last;
        while (--i > first) {        // (shift, first]
            if (*i < *(i-1)) {
                std::iter_swap(i, i-1);
                shift = i;
            }
        }
        first = shift;
    }
}

바깥 고리[편집]