Sorting : Bubble | Selection | Insertion : How to analyze time and space Complexity

Question

I have coded following programs (Bubble, Selection, Insertion) and I want to check their Time and Space complexity. Can any one please guide me whether they are correct as most of the programs on internet/books are with Arrays not ArrayList.

    public class BubbleSort {

      List<Integer> unsortedList;

      private BubbleSort() {
        unsortedList = new ArrayList<Integer>();
        unsortedList.add(0, 6);
        unsortedList.add(1, 3);
        unsortedList.add(2, 7);
        unsortedList.add(3, 4);
        unsortedList.add(4, 2);
        unsortedList.add(5, 3);
        unsortedList.add(6, 8);
    }

    private void sortData() {
        ArrayList<Integer> tempList = (ArrayList<Integer>) this.unsortedList;
        int size = unsortedList.size();
        int counter = size;
        do {

            for (int i = 0; i < size-1; i++) {

                if (unsortedList.get(i) > unsortedList.get(i + 1)) {


                    Integer temp1= unsortedList.get(i + 1);
                    Integer temp2= unsortedList.get(i);
                    unsortedList.set(i,temp1);
                    unsortedList.set(i+1,temp2);

                }
            }
            size = size - 1;
        } while (size != 1);
    }

    public static void main(String arg[]) {

        BubbleSort obj = new BubbleSort();
        obj.sortData();

        for(Integer i:obj.unsortedList){
            System.out.println(i);
        }
    }}

    public class SelectionSort {

    List<Integer> unsortedList;

    private SelectionSort() {
        unsortedList = new ArrayList<Integer>();
        unsortedList.add(0, 16);
        unsortedList.add(1, 3);
        unsortedList.add(2, 7);
        unsortedList.add(3, 4);
        unsortedList.add(4, 12);
        unsortedList.add(5, 3);
        unsortedList.add(6, 8);
        unsortedList.add(7, 18);
        unsortedList.add(8, 81);
        unsortedList.add(9, 2);
    }

    public void sortData() {

    int totalPass = unsortedList.size();
    int listLength = totalPass;

    for (int i = 0; i <= totalPass - 1; i++) {
        int pointerSmallPosition=i;
        for (int j = i; j < listLength-1; j++) {

            if (unsortedList.get(pointerSmallPosition) > unsortedList.get(j + 1)) {
                pointerSmallPosition=j + 1;
            }
        }

        int temp1= unsortedList.get(i);
        int temp2= unsortedList.get(pointerSmallPosition);
        unsortedList.set(i,temp2);
        unsortedList.set(pointerSmallPosition,temp1); 
    }

}

public static void main(String arg[]) {

    SelectionSort obj = new SelectionSort();
    obj.sortData();

    for (Integer i : obj.unsortedList) {
        System.out.println(i);
    }
}}

 public class InsertionSort {

    List<Integer> unsortedList;

    public InsertionSort(){
        unsortedList = new ArrayList<Integer>();
        unsortedList.add(0, 6);
        unsortedList.add(1, 3);
        unsortedList.add(2, 7);
        unsortedList.add(3, 4);
        unsortedList.add(4, 2);
        unsortedList.add(5, 3);
        unsortedList.add(6, 8);
    }

    public static void main(String arg[]){

        InsertionSort obj=new InsertionSort();
        obj.sortData();

        for(Integer i:obj.unsortedList){
            System.out.println(i);
        }

    }

    private void sortData() {

        int size = unsortedList.size();
        int sortedSize=0;
        for(int i=1;i<size-1;i++){
            int j=i;
            do{
                if(unsortedList.get(j)<unsortedList.get(j-1)){
                    int small=unsortedList.get(j);
                    int large=unsortedList.get(j-1);
                    unsortedList.set(j-1, small);
                    unsortedList.set(j, large);
                }
                j--;
            }while(j>sortedSize);

        }}}

These are standard algorithms and time and space have been asymptotically evaluated: https://en.wikipedia.org/wiki/Introduction_to_Algorithms If you want to measure speed on yours, use http://stackoverflow.com/questions/351565/system-currenttimemillis-vs-system-nanotime but that would be different on different machines. You sould use large lists (many items) to get more or less meaningful results. I hope Collections.sort may be helpful since it implements optimized alg — Antonio, Jul 28 '15 at 15:11
Asking us to ask whether your code is correct is off topic. If you want to know the time complexity, you should stick to one code sample per question. Perhaps you should try to get a deeper understanding of ArrayLists - if you know the time complexity with arrays, and you understand ArrayLists, you should be able to figure out the complexity with ArrayLists easy enough (it will often be exactly the same, although there are opportunities to do things in an easier, but less efficient, way with ArrayLists). — Bernhard Barker, Jul 28 '15 at 15:45
They're all O(n^3) owing to the get/set methods which are O(n) access time. — dan, Jul 28 '15 at 20:23
Yes I have got the point of working with Collections and Arrays, Cost of Collections is much more than Arrays. Not a good question to continue. — Navdeep Singh, Jul 29 '15 at 14:51
I'm voting to close this question as off-topic because this should have to be posted to code review website — Navdeep Singh, Jul 29 '15 at 14:58

score 0 · Answer 1 · edited May 23 '17 at 11:51

To analyze complexity you can use Big O notation. I linked you to a table that can help you understand the theory on it. Using ArrayList doesn't really matter in Big O; you just have to "care about the main process" of your algorithms. In your examples are the Loops what defines the N or N^x ...

If you want to see the time your algorithm use to finish, you can use the post that Antonio said.

Sorting : Bubble | Selection | Insertion : How to analyze time and space Complexity

1 Answers1