Best and worst case runtimes of my search algorithm (similar to bubble sort)?

Question

So I know this algorithm is pretty simple, but I can't wrap my head around the time complexity of the code. It takes in an array (say 5 numbers) and sorts it in increasing order and in a similar manner to bubble sort (but not quite the same). What are the best and worst case runtimes of this algorithm?

int sort(int arr[1...n]){
  while(i <= n){
    k = n;
    while(k >= i+1){
      if (arr[k-1] > arr[k]){
        tmp = arr[k-1];
        arr[k-1] = arr[k];
        arr[k] = tmp;
      }
      k--;
    }
    i++;
  }
}

My reasoning:

The worst case would be if the array was in reverse sorted order, say [5,4,3,2,1]. I know the outer while loop would be executed n times, but the inner while loop is what throws me off. For each iteration of the outer while, I think the inner while executes i+1 times, so with the array I gave, it would execute the inner while 4,3,2,and then finally 1 time (that's a total of (n-1) executions of the inner while loop)...Putting it together I have n*(n-1), so does that mean worst case is O(n^2)?

The best case is when the array is already sorted, say [1,2,3,4,5].So in that case we would never need to do nay swapping of numbers, and the if statement in the inner while is never executed. But the code seems to loop through everything despite the fact that the array is already sorted. We still go through both while loops which leads me to believe it's still n*(n-1), but that seems off to me. Any help is appreciated.

You could run the code and instrument it a bit to collect how often the loops run for different inputs? http://jsbin.com/gogesunaki/edit?js,console — Karl Reid, Jun 08 '17 at 16:45
@KarlReid It is not possible to determine algorithmic complexity by empirical analysis. See [this answer](https://stackoverflow.com/a/4852666/3225495). — BJ Myers, Jun 08 '17 at 16:50
Very interesting, thanks for that. I always thought you could get a 'feel' for the complexity at least by looking at some runs with different inputs. Maybe this is why I fail all my interviews :) — Karl Reid, Jun 08 '17 at 16:51
@BJMyers no, but we can compute a likely estimate with numerical analysis and curve fitting, see: http://dl.acm.org/citation.cfm?id=2899443 — Centril, Jun 08 '17 at 17:00

score 1 · Answer 1 · answered Jun 08 '17 at 16:53

1

In the worst case there will be 1+2+3+...(n-1) iterations, so that's n(n-1)/2 => n^2/2 - n/2.

Neglecting the constants, the algorithm is of worst case O(n^2 - n) complexity, which is just O(n^2).

answered Jun 08 '17 at 16:53

four_lines

503
3
12

So that means I had the right idea then correct? Because `n(n-1) = n^2 -n` – Vekktone Official Jun 08 '17 at 16:54
1

Tho, this reasoning is kinda hand-wavy... if you were to actually prove this, you'd have to set up sums and solve them... – Centril Jun 08 '17 at 16:57
@VekktoneOfficial Yeah that's correct. Also, practically you can reduce time with this: If no conditions in an iteration of `i` are true, you can stop your process entirely. Since the array is already in a sorted condition. So your best case becomes `O(n)` – four_lines Jun 08 '17 at 16:59
okay, I think I understand that, but in the code above, wouldn't the inner while loop still execute no matter what the conditions of iteration `i` are? – Vekktone Official Jun 08 '17 at 17:08
@VekktoneOfficial Just stop the iteration of the outer loop once you realize that the condition has never been true in the outer loop iteration. – four_lines Jun 08 '17 at 17:12

score 0 · Answer 2 · answered Jun 08 '17 at 22:12

It's no surprise that the code "loops through everything," even when the array is already sorted. You don't tell it not to.

You need to add a sentinel value that tells it stop when the array is already sorted.

In your code, if the internal if statement is never entered during a single pass, then you know that the array is sorted. So what you do is initialize a flag at the start of each iteration of the outer loop. If the if statement is ever entered, then you set the flag. If, the flag is not set at the end of the out loop iteration, then you know that the array is sorted. Here's the code:

int sort(int arr[1...n]){
  bool didSwap = true;
  while(i <= n && didSwap){
    didSwap = false;
    k = n;
    while(k >= i+1){
      if (arr[k-1] > arr[k]){
        tmp = arr[k-1];
        arr[k-1] = arr[k];
        arr[k] = tmp;
        didSwap = true;
      }
      k--;
    }
    i++;
  }
}

That will make your code "early out" when the array is sorted.

Best and worst case runtimes of my search algorithm (similar to bubble sort)?

2 Answers2