Algorithm of Bubble sort optimised way

Question

I have 2 different codes for sorting an array:

    static void bubbleSort2(int[] arr){
        System.out.println( "bubble starts ");
        int  tmp =0;int cnt =0;
        for (int i=0; i< arr.length-1 ; i++){
            for (int j=i+1; j< arr.length ; j++){
                if(arr[i] > arr[j]){
                    tmp = arr[j];
                    arr[j]=arr[i];
                    arr[i] = tmp ;
                }
                cnt++;
            }
            printMe(arr);

        }
        System.out.println("Bubble cnt="+cnt);
        printMe(arr);
    }

And:

    static void bubbleSort(int a[])
    {
        int len = a.length; 
        int cnt=0;
        System.out.println( "bubble starts ");

        for (int i = 0; i < len-1; i++){
            for (int j = 0; j < len-i-1; j++) {
                if (a[j] > a[j+1]) 
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            cnt++;
            }
            printMe(a);
        }
        System.out.println("Bubble cnt="+cnt);
        printMe(a);
    }

bubbleSort2 is written by me, and I find it is printing the cnt value more than what the bubbleSort function is printing .

Below is the output for array --> int[] bbArr= { 28,6,4,2,24 };

    bubbleSort(bbArr);
    bubbleSort2(ccArr);

bubble starts 

    6,4,2,24,28
    4,2,6,24,28
    2,4,6,24,28
    2,4,6,24,28
    Bubble cnt=10

bubble starts 

    2,28,6,4,24
    2,4,28,6,24
    2,4,6,28,24
    2,4,6,24,28
    Bubble cnt=10

I see that one method keeps sorting from the starting position, while the other method keeps sorting from the last position of array. Does it really matter the order of sorting in a particular sorting algo?

trincot · Accepted Answer · 2023-07-13 21:08:01Z

2

Your code is not implementing bubble sort, but a kind of selection sort.

One characteristic of bubble sort is that it only swaps adjacent values. Your algorithm swaps values that can be far apart.

You are right that standard bubble sort will grow a sorted partition at the right side of the array, while standard selection sort will grow a sorted partition at the left side of the array. (Obviously, these algorithms can be made to run in the opposite direction).

I find it is printing the cnt value more than what the bubbleSort function is printing.

It is not more. Both of your functions execute a predictable number of comparisons which only depends on the size of the input array, not on the actual contents: 𝑛(𝑛−1)/2

Does it really matter the order of sorting in a particular sorting algo ?

When comparing these two algorithms, it doesn't matter. But more importantly though, these two sorting algorithms do not perform well when the input array is large. For relatively large arrays you'll get better run times with sorting algorithms that have an average complexity of O(𝑛log𝑛), such as quick sort, merge sort, heap sort,...

edited Jul 13, 2023 at 21:08

answered Jul 13, 2023 at 20:58

trincot

357k38 gold badges282 silver badges338 bronze badges

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

6 Comments

Jim Mischel Over a year ago

Minor nit: the order or sorting does matter, even when comparing these two algorithms. With a minor modification, Bubblesort can be made to early out, making the best case O(n). Average and worst case are of course O(n^2). Selection sort, however is always O(n^2); there is no potential for early out.

trincot Over a year ago

@Jim, I was considering the code as presented, without any minor modification. The code presented by the asker has a predictable number of comparisons.

summary Over a year ago

@trincot : the cnt value mismatch was my mistake in typing the code. I forgot to add parentheses around inner for loop . cnt value is same for both . thanks for explaining the answer so well.

trincot Over a year ago

Sorry, but I have to disagree. Also Wikipedia states that Bubble sort constitutes of "comparing the current element with the one after it". Your code is not doing that. Your code is looking at the subarray after the current index of the outer loop to eventually swap the least element into slot i. That is a hallmark of selection sort. Wikipedia says about it "The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist"

Jim Mischel Over a year ago

@summary Bubblesort is characterized by the larger elements being swapped (bubbled) towards the end of the array. That's what the code in your bubbleSort does, as you can see by the output you provide. Selection sort is characterized by finding the largest item, swapping it to the first, the next largest, swapping it to the second, etc. Which is what your bubbleSort2 does. The algorithms are vastly different. bubbleSort2 is not by any definition a bubble sort.

|

Collectives™ on Stack Overflow

Algorithm of Bubble sort optimised way

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related