3

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

Improve this question
3
  • Apparently, the first one doesn't even work correctly: FINAL 12,4,22,45,78 Commented Aug 14, 2015 at 11:27
  • "sorting algorithm is worst that n^2." - did he mean that the worst case complexity is O(n²), or did he mean that (some) complexity is worse than O(n²)? Commented Aug 14, 2015 at 11:32
  • Thats what the interviewer said, that my first solution was worst that n raise to 2 Commented Aug 14, 2015 at 11:36

4 Answers 4

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I think the first one is actually O(n^3), as you linearly search through the array to find one swap. And with O(n^2) swaps you arrive at O(n^3) compares.
@Tali I think you're right. I've corrected my 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.

Improve this answer

Comments

1

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.

Improve this answer

10 Comments

The first one is also bubble sort.
@IVlad yes but not the typical implementation I also note in my answer that the two solutions are asymptotically equivalent
@IVlad: Apart from the fact that a bubble sort actually sorts an array :-)
@IVlad actually I take that back. Note where isSwipe is changing in first solution. First solution is not quadratic at all. It misses a cycle
Well, barring implementation mistakes. I didn't run the code. What do you mean about where isSwipe is changing? It doesn't miss a cycle because the iteration variable gets reset (num).
|
1

  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.

Improve this answer

1 Comment

1. First solution is wrong and it is not a correct sorting algorithm. 2. You can improve a slow sorting algorithm - look up cocktail sort.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.