0
\$\begingroup\$

I have a simple integer sorting problem at hand and to solve it, I am planning to write a variation of bubble sort. It seems to be working fine but I am not sure about it's complexity in big-O. What it could be ?

public class TempBubbleSort 
{

static Integer[] myArray = {10,9,8,7,6,5,4,3,2,1};

static int counter = 0;

public static void main(String[] args)
{
    for(int anchor=0; anchor<myArray.length; anchor++)
    {
        for(int compare=anchor+1; compare<myArray.length; compare++)
        {
            counter++;
            // sort ascending
            if(myArray[anchor] > myArray[compare])
            {
                int tmp = myArray[compare];
                myArray[compare] = myArray[anchor];
                myArray[anchor] = tmp;
            }
        }
    }

    System.out.println("Comparision Count : "+counter);

    for(int i : myArray)
        System.out.println(i);
}


}

Output when you run above is :

Comparision Count : 45
1
2
3
4
5
6
7
8
9
10
\$\endgroup\$
  • \$\begingroup\$ There already better sorting algorithms which you can just use. Why struggling with writing worse on your own? \$\endgroup\$ – πάντα ῥεῖ Nov 10 '19 at 11:28
  • \$\begingroup\$ Also note that static Integer[] myArray = {10,9,8,7,6,5,4,3,2,1}; hits an edge case. \$\endgroup\$ – πάντα ῥεῖ Nov 10 '19 at 11:40
  • \$\begingroup\$ Agreed with @πάνταῥεῖ. I realize that what I had written is more similar selection sort than bubble. And complexity will in closer to selection sort. Thanks for your input. \$\endgroup\$ – Dhaval D Nov 10 '19 at 12:02
3
\$\begingroup\$

Strictly answering your question about what the \$Big-O\$ run-time complexity,

public class TempBubbleSort 
{

static Integer[] myArray = {10,9,8,7,6,5,4,3,2,1};

static int counter = 0;

public static void main(String[] args)
{
    // **This is O(n), as we're touching every point in your array.
    for(int anchor=0; anchor<myArray.length; anchor++)
    {
        // **This is O(n-1), but since we don't care about constants as n grows, we consider this as O(n)
        for(int compare=anchor+1; compare<myArray.length; compare++)
        {
            // **Everything in here then is a bunch of constant operations so we'll just ignore them.
            counter++;
            // sort ascending
            if(myArray[anchor] > myArray[compare])
            {
                int tmp = myArray[compare];
                myArray[compare] = myArray[anchor];
                myArray[anchor] = tmp;
            }
        }
    }
    // **So the total of the brunt of your work would be O(n)*O(n) or O(n^2), because for every element in your array n, you touch every other element in your array, so you can look at it as touching n things in your array, n times.

    System.out.println("Comparision Count : "+counter);

    // **In case you're curious, this is also O(n)
    for(int i : myArray)
        System.out.println(i);

    // **Which would bring the grand total to O(n^2+n), again with Big O notation, we only care about what happens as n continues to grow, and since n^2 grows faster than n, as our n gets super big, the second term n becomes insignificant, so we look at this overall total as O(n^2). In fact, for any polynomial time complexity, you can safely drop all terms that are not your largest degree.
}


}

In closing, its usually easy to tell the time-complexity of simple iterative functions like this by the number of nested for loops you have, which can be a good rule of thumb for a nice approximate guess for time complexity in a pinch.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.