4 ms·
Two loops: (I'm sure I'll get this wrong.) for (int ii = 0; ii < n-1; ++ii) { // ii+1 largest elements end up in their correct position at the end of thi
by swolchok 18y ago
Two loops: (I'm sure I'll get this wrong.)
for (int ii = 0; ii < n-1; ++ii) {
// ii+1 largest elements end up in their correct position at the end of this loop.
for (int jj = ii; jj < n-1; ++jj) {
if (arr[jj] > arr[jj+1]) {
swap(arr[jj], arr[jj+1]);
}
}
}
One loop:
int ii, jj;
for (ii = 0, jj = 0; ii < n-1; ii = ((jj == (n-1)) ? (ii + 1) : ii), jj = ((jj == n-1) ? ii : (jj + 1))) {
// compare and swap as before
}
Unreadable, but it's one loop.
EDIT: use code formatting, oops.
EDIT 2: add proper conditional for jj update instead of jj = jj + 1.
- lacker 18y agoNot really bubble-sort-specific; you can make any pair of loops into a single loop that way. for (set up initial conditions for both loops; check the outer loop termination condition; if the inner loop is done reset the inner loop and advance the outer loop, if the inner loop is not done advance the inner loop) { // do the inside of the loop }
- jermy 18y agoAt least one of those loops in the 2-loop version should be backwards... :)