bubble sort

bubble-sort.cpp

//
// BUBBLE-SORT
//
// loop-invariant:
//
// the right-most i elements are the largest i elements in A[0:N), 0<=i<N
// sorted in ascending order
//
void bubble_sort1(vector<int>& A){
    bool swapped;
    do {
        swapped=false;
        for (int i=1,N=(int)A.size(); i<N; ++i)
            if (A[i-1] > A[i]){
                swap(A[i-1],A[i]);
                swapped=true;
            }
    } while (swapped);
}

void bubble_sort2(vector<int>& A){
    bool swapped;
    do {
        swapped=false;
        for (auto itr=A.begin(); itr!=A.end() && itr!=prev(A.end()); ++itr)
            if (*itr > *next(itr)){
                iter_swap(itr,next(itr));
                swapped=true;
            }
    } while (swapped);
}