Skip to content

Instantly share code, notes, and snippets.

@claytonjwong
Last active August 19, 2022 21:19
Show Gist options
  • Save claytonjwong/d39cc30ae075c7b9f796ef896627d471 to your computer and use it in GitHub Desktop.
Save claytonjwong/d39cc30ae075c7b9f796ef896627d471 to your computer and use it in GitHub Desktop.
bubble sort
//
// 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment