CODEWITHSUNDEEP
javaalgorithmsortingbubble-sort
Ren
Ren

Reputation: 39

counting comparisons in optimized bubble sort algorithm

As the title says, i need to count how many comparisons i have while sorting a given array with the optimzed bubble sort algorithm.

The problem is, I get 45 as a result, when the output should be 31 (for the array given in the main). I also tried setting the upper bound for the second inner loop to the last index where a comparison was made, but it's not correct still.

`

public class Main{
    public static int optimizedBubbleSort(int[] arr) {
        int n = arr.length;
        int comparisons = 0;

        // Set flag for whether the list is already sorted
        boolean sorted = false;

        // Keep looping until the list is sorted
        while (!sorted) {
            sorted = true;
            int lastSwapIndex = 0;

            // Loop through the list and compare adjacent elements
            for (int i = 0; i < n - 1; i++) {
                comparisons++;
                if (arr[i] < arr[i + 1]) {
                    // If an element is out of order, swap it and set the sorted flag to false
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    sorted = false;
                    lastSwapIndex = i;
                }
            }

            // Set the upper bound for the second inner loop to the last index where a swap was made
            n = lastSwapIndex + 1;
        }

        // Return the number of comparisons made
        return comparisons;
    }

    public static void main(String[] args) {
        int[] arr = {10, 42, 27, 17, 58, 39, 91, 19, 42, 66};
        int comparisons = optimizedBubbleSort(arr);
        System.out.println("Number of comparisons: " + comparisons);
    }
}

`

Upvotes: 0

Views: 144

Answers (1)

Nelfeal
Nelfeal

Reputation: 13269

You are sorting the array in descending order. Your condition arr[i] < arr[i + 1] means you swap elements if the second is greater than the first, so you place the greater number first. This does indeed do 45 comparisons on the example array you have.

Simply change your condition to arr[i] > arr[i + 1] to sort in ascending order, doing 32 (not 31) comparisons instead.

Upvotes: 3

Related Questions