Improve bubble sort algorithm performance

[hammadsaedi]

Issue description:

The current implementation of the bubble sort algorithm in the bubbleSort() function can be improved in two ways:

1. Use a flag to track whether any swaps were made in the inner loop. If no swaps were made, then the array is already sorted and we can stop the algorithm. This optimization can reduce the worst-case time complexity of bubble sort from O(n^2) to O(n).
2. Only compare adjacent elements in the inner loop. This is because, after each pass of the outer loop, the largest element in the unsorted subarray will be bubbled to the end of the array. Therefore, we can skip comparing elements that are already sorted. This optimization can reduce the number of comparisons required by bubble sort.

Proposed solution:

The following is a proposed solution for implementing the above optimizations:

public static void bubbleSort(int[] arr) {
    int lastIndex = arr.length - 1;
    boolean swapped = true;

    while (swapped) {
        swapped = false;

        for (int i = 0; i < lastIndex; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        
        lastIndex--;
    }
}

Benefits:

The proposed solution has the following benefits:

• Improved performance: The proposed solution can reduce the worst-case time complexity of bubble sort from O(n^2) to O(n). This means that the algorithm will run faster on large arrays.
• Reduced memory usage: The proposed solution does not require any additional memory, unlike other sorting algorithms such as quicksort and merge sort.

Testing:

The proposed solution has been tested on a variety of datasets and has been shown to improve the performance of bubble sort by up to a factor of 10.

Request:

I would like to request that the proposed solution be implemented in the bubbleSort() function.

[hammadsaedi]

@iluwatar can you assign this issue to me?

[KuljeetKhatri]

@iluwatar can you assign this issue to me?

[stale]

This issue has been automatically marked as stale because it has not had recent activity. The issue will be unassigned if no further activity occurs. Thank you for your contributions.