CODEWITHSUNDEEP
arraysalgorithmsorting
Vekktone Official
Vekktone Official

Reputation: 57

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

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.

Upvotes: 0

Views: 208

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134015

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.

Upvotes: 0

four_lines
four_lines

Reputation: 503

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

Upvotes: 1

Related Questions