3 ms·
No, I don't miss them, but I'm sure glad I had to suffer through them. It has helped me to understand "what's happening under the hood" when I make a call with
by edw519 18y ago
No, I don't miss them, but I'm sure glad I had to suffer through them. It has helped me to understand "what's happening under the hood" when I make a call with one line of code.
I used to screen programmers by having them code a bubble sort in 20 minutes. After about 1000 of these, I think the results were:
Pct Result
----- ---------------------------------------
50.0 Why would anyone ever want to to that?
25.0 Tried but couldn't do it
24.9 Did it in 2 loops
.1 Did it in 1 loop (Yes, I hired him.)
- nradov 18y agoOK, I'll bite. How do you do it in one loop?
- swolchok 18y agoTwo 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... :)