What should be the time complexity of my sorting algorithm?

Question

Yesterday I went for an interview,

He asked me to write a program to sort an array in ascending order.

I wrote a program which is as follows,

var mySortOne = function(myArray){
    var num = 0,
        temp = 0, 
        isSwipe = false,
        counter = 0;    

    for(num = 0; num < myArray.length; num++){
        print((++counter)+" => "+myArray);
        if (((num+1) < myArray.length) && (myArray[num] > myArray[num+1])){
            temp = myArray[num+1];
            myArray[num + 1] = myArray[num];
            myArray[num] = temp;
            isSwipe = true; 
        }
        if(isSwipe){
            isSwipe = false;
            num = -1;
        }
    }

    print("\n FINAL "+myArray);
};

mySortOne([45,12,78,22,4]);

The interviewer was not satisfied, he said "I am not asking for optimum solution, but your sorting algorithm is worst that n^2."

So I wrote a second solution, which is as follows,

var mySortTwo = function(myArray){
    var num = 0,
        MAX = myArray.length,
        isSwipe = false,
        temp = 0,
        counter = 0;

    do{
        isSwipe = false;
        for(num = 0; num < MAX; num++){
            print((++counter)+" => "+myArray);
            if(((num + 1) < MAX) && (myArray[num] > myArray[num+1])){
                temp = myArray[num + 1];
                myArray[num + 1] = myArray[num];
                myArray[num] = temp;
                isSwipe = true;              
            }
        }
        MAX--;
    }while(isSwipe);

    print("\n FINAL "+myArray);
};

mySortTwo([45,12,78,22,4]);

But still he was not satisfied.

I had some print statements of both the algorithm.

The first algorithm's output is

1 => 45,12,78,22,4
2 => 12,45,78,22,4
3 => 12,45,78,22,4
4 => 12,45,78,22,4
5 => 12,45,22,78,4
6 => 12,45,22,78,4
7 => 12,22,45,78,4
8 => 12,22,45,78,4
9 => 12,22,45,78,4
10 => 12,22,45,78,4
11 => 12,22,45,4,78
12 => 12,22,45,4,78
13 => 12,22,45,4,78
14 => 12,22,4,45,78
15 => 12,22,4,45,78
16 => 12,4,22,45,78
17 => 4,12,22,45,78
18 => 4,12,22,45,78
19 => 4,12,22,45,78
20 => 4,12,22,45,78
21 => 4,12,22,45,78

 FINAL 4,12,22,45,78

And the output of second algorithm is as follows,

1 => 45,12,78,22,4
2 => 12,45,78,22,4
3 => 12,45,78,22,4
4 => 12,45,22,78,4
5 => 12,45,22,4,78
6 => 12,45,22,4,78
7 => 12,45,22,4,78
8 => 12,22,45,4,78
9 => 12,22,4,45,78
10 => 12,22,4,45,78
11 => 12,22,4,45,78
12 => 12,4,22,45,78
13 => 12,4,22,45,78
14 => 4,12,22,45,78
15 => 4,12,22,45,78

 FINAL 4,12,22,45,78

He said both are iterating too much. We can have a better solution using simple bubble sort.

But what I think is my second solution is a bubble sort itself.

Can you please tell me what are the complexity for both the algorithms, and how come I can improve the second bubble sort

Answer 1

You tried to implement bubble sort and your second sort is correct bubble sort and first one looks like bubble sort but is extremely inefficient. I'll make a few points about your first algorithm.

1. When someone says an algorithm is O(n^2) what they mean is the time it take will be proportional to n^2, so when you double n, time will become 4 times (roughly). This is because the number of loops increaseing. i.e. for O(n^2) there are n loops, with each loop iterating n times or less. In bubble sort, in every loop multiple swaps happen. In your case, in every swap a new loop is started. So the complexity has increase by one magnitude. So your algorithm is O(n^3).

2. the isSwipe you used is one of the best things about bubble sort. It gives the algorithm the ability to detect if the array is sorted and stop further processing. So the best case complexity becomes o(n) but in selection sort its still o(n^2). In your case the isSwipe has been rendered useless. Since it is set to true inside the comparison, it becomes true when the comparison returns true, and since n is set to -1 if isSwipe is true, n is set to -1 if the comparison returns true. So I can change your algorithm to this and it would give the same result:

   var mySortOne = function(myArray){
       var num = 0,
       temp = 0, 
       isSwipe = false,
       counter = 0;    
   
       for(num = 0; num < myArray.length; num++){
           print((++counter)+" => "+myArray);
           if (((num+1) < myArray.length) && (myArray[num] > myArray[num+1])){
               temp = myArray[num+1];
               myArray[num + 1] = myArray[num];
               myArray[num] = temp;
               num = -1;
           }
       }
       print("\n FINAL "+myArray);
   };
   

   or in short, you are not using isSwipe at all.

About your second algorithm, your interviewer was right. It's not a simple bubble sort, it's an optimised bubble sort. Which means that your algorithm gives better performance than simple bubble sort which would have kept comparing the sorted elements in the end by not having the MAX-- step. So he is right that it's not a simple bubble sort, but wrong that a simple one would have been better. So you just one upped him. Congratulations and don't let anybody tell you that your second algorithm is not bubble sort.

Answer 2

Both of your algorithms are Bubble sort, because you compare and swap adjacent elements. I didn't check if they actually work, but at least the intended logic looks right.

The first one, contrary to appearances, is intended to be Bubble sort. The number of for loops does not dictate the number of iterations. See here for an example of a Bubble sort that uses a single loop.

Your first implementation does look to be O(n^3) however, because you reset the iteration variable after each swap. If you insist on using a single loop, I suggest you loop until n^2 and eliminate the reset you're doing, like you can see in the previous link. Thanks to Tali for pointing this out.

Your second one is pretty well optimized for a bubble sort, but you can do more. Note that in bubble sort, the optimal element (max or min) gets to its final position after a run of the inner loop. So, for next iterations, you only need to iterate up until the position of the last swap in the previous iteration.

do{
    isSwipe = false;
    newMax = 0;
    for(num = 0; num < MAX; num++){
        print((++counter)+" => "+myArray);
        if(((num + 1) < MAX) && (myArray[num] > myArray[num+1])){
            temp = myArray[num + 1];
            myArray[num + 1] = myArray[num];
            myArray[num] = temp;
            isSwipe = true;              
            newMax = i + 1; ///////////////////// here //////////////////// 
         }
    }
    MAX = newMax;
    // no need for this anymore MAX--;
}while(isSwipe);

But it will still be quadratic. It is an optimization you could have done, however.

A more advanced optimization is Cocktail sort, but this is also quadratic in the worst case.

Answer 3

1. Yes, both of your algorithms are iterating too much. They have a complexity of O(n*n). In case of little n - your algorithm is good. However, this JSFiddle shows that for n = 100000, MergeSort sorts an array for 263ms while your sort takes 100 times more - 23901ms (24 seconds!) to complete.

2. Both algorithms are kinds of BubbleSort. However, your code is overcomplicated while having the same complexity. As I guess, "We can have a better solution using simple bubble sort" means "We could write a simple BubbleSort and have the same result".

3. Improving a slow sorting algorithm is, probably, not the best option. You can choose another one. There are a lot of algorithms which work for O(n*log(n)). As for me, I prefer MergeSort and HeapSort because I forget how actually QuickSort works. Moreover, MergeSort is a stable sort algorithm.

Answer 4

The second algorithm is bubble sort. I think the interviewer was wrong. However the first solution is flawed and is not a correct sorting implementation. You need one more cycle at the very least.