Why bubble sort is taking more time then selection sort

Question

I am trying various scenarios with bubble sort and selection sort. I know that the best case for bubble sort is O(n) if we use break statement. But lets say even if I am not using any break statement, there will not be any swaps (as we have if condition for it), and it should take same or less time as selection sort.

But strangely its taking more time for me.

Note : I have taken same data set(1 to 900000) which is already sorted. And as I am using already sorted data set, none of the algorithms will have any swappings.

Please find the program below :

 package sorting;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.List;

public class Sorting<Item extends Comparable>//this Item is a var/field which can only be find while creatng a object and hence it is non static
{

    List<Item> list=new ArrayList<Item>();

    public static void main(String args[])
    {

        Sorting<Integer> ss=new Sorting<Integer>();

        System.out.println("adding item logic started : "+Calendar.getInstance().getTime());
        for(int i=0;i<90000;i++)
        {
            ss.list.add(i);

        }
        System.out.println("adding item logic ended : "+Calendar.getInstance().getTime());
        //selection sort started
        Calendar c1=Calendar.getInstance();
        System.out.println(c1.getTime());
        ss.selectionSort(ss.list);

        Calendar c2=Calendar.getInstance();
        System.out.println(c2.getTime());
        System.out.println("selection sort time taken in seconds : "+(c2.getTimeInMillis()-c1.getTimeInMillis())/1000);
    //  System.out.println(ss.list);


        //bubble sort started
        ss.list=new ArrayList<Integer>();
        for(int i=0;i<90000;i++)
        {
            ss.list.add(i);

        }
        Calendar c3=Calendar.getInstance();
        System.out.println(c3.getTime());
        ss.bubbleSort(ss.list);

        Calendar c4=Calendar.getInstance();
        System.out.println(c4.getTime());
        System.out.println("bubble sort time taken in seconds : "+(c4.getTimeInMillis()-c3.getTimeInMillis())/1000);
    //  System.out.println(ss.list);
    }

    void selectionSort(List<Integer> list)
    {
        for(int i=0;i<list.size();i++)
        {
            int target=(Integer)list.get(i);
            int pos=0;

            for(int j=i+1;j<list.size();j++)
            {//System.out.println(i+"  "+j);
                if(target>(Integer)list.get(j))
                {
                    pos=j;
                    target=(Integer)list.get(j);
                }
            }
            if(pos!=0)
            {
                Integer temp=(Integer)list.get(i);
                list.set(i, (Integer)list.get(pos));
                list.set(pos, temp);


            }



        }
    }

    void bubbleSort(List<Integer> list)
    {

        for(int i=list.size()-1;i>0;i--)
        {
            int status=0;
            for(int j=0;j<=i-1;j++)
            {
                //System.out.println(i+"  "+j);
                if((Integer)list.get(j)>(Integer)list.get(j+1))
                {
                    int temp=(Integer)list.get(j+1);
                    list.set(j+1, (Integer)list.get(j));
                    list.set(j, temp);
                    status++;
                }
            }
            //if(status==0)break;
        }
    }
}

This program is 85 percent giving more time for bubble sort and sometimes it double of what insertion sort is taking.

adding item logic started : Fri Jun 26 02:47:13 PDT 2015
adding item logic ended : Fri Jun 26 02:47:13 PDT 2015
Fri Jun 26 02:47:13 PDT 2015
Fri Jun 26 02:47:58 PDT 2015
selection sort time taken in seconds : 44
Fri Jun 26 02:47:58 PDT 2015
Fri Jun 26 02:48:46 PDT 2015
bubble sort time taken in seconds : 56

Answer 1

Well, as I see in your code, the number of iterations in both algorithms will be the same

for(int i=0;i<list.size();i++)
    for(int j=i+1;j<list.size();j++)

would be the same as

for(int i=list.size()-1;i>0;i--)
    for(int j=0;j<=i-1;j++)

so the difference should rely on what's happening inside each iteration (I will just be taking the inner part of the loop, the other we will omit).

In bubble sort:

if((Integer)list.get(j)>(Integer)list.get(j+1))
{
    int temp=(Integer)list.get(j+1);
    list.set(j+1, (Integer)list.get(j));
    list.set(j, temp);
    status++;
}

as the list is sorted, you won't get inside the if, so you have two list.get(something).

In selection sort:

if(target>(Integer)list.get(j))
{
    pos=j;
    target=(Integer)list.get(j);
}

but you won't get inside the if, so you only get one list.get(something).

In short, with selection sort you are doing less operations in each iteration, that may be what makes your program to run faster.

Answer 2

You mix up complexity and running time.

For example if you have one algorithm, that always takes one hour, this algorithm has a complexity of O(1). A second algorithm takes 1 minute for 1 element, 2 minutes for 2 elements, 3 minutes for 3 elements, ... This algorithm has a complexity of O(n). Complexity-wise the first algorithm is better, but for 1 to 59 elements the second algorithm is faster.

Answer 3

To give a simple example here the are two cases In Bubble Sort

First Pass:
( 5 1 4 2 8 ) \to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )

Where as in Selection sort

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

AS seen in the bubble sort there are three passes happen where as in the selection sort theres only a single pass

Answer 4

You say:

"But lets say even if I am not using any break statement, there will not be any swaps (as we have if condition for it), and it should take same or less time as selection sort."

In your code you comment out the break statement in the outer loop:

//if(status==0)break;

Without the break statement, the algorithm/code is O(n^2), and you aren't getting any benefit from it being sorted.