Hacker News Reader

Comment by edw519 | Hacker News Reader

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.)

View on HN

OK, I'll bite. How do you do it in one loop?

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.

Not 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
  }

At least one of those loops in the 2-loop version should be backwards... :)

Reply on news.ycombinator.com