Bubble Sort compares adjacent elements and swaps them if they are in the
wrong order. This process is repeated until the array is sorted.
Time Complexity
Worst Case: O(n^2) -This occurs when the input array is in reverse order.
In each iteration of the outer loop, the inner loop will compare and
potentially swap each of the remaining unsorted elements. This leads to
approximately n(n-1)/2 operations, which is the order of O(n^2).
Average Case: O(n^2) - On average, bubble sort will still need to perform a
quadratic number of operations. This is because, on average, it will still
need to perform roughly half of the comparisons and swaps as in the worst-case
scenario for any given random array.
Best Case: O(n) - This occurs when the input array is already sorted.
In the best case (when an optimized version of bubble sort is used that
terminates early if no swaps were made in a pass), only n-1 comparisons will
be made and no swaps. Hence the best case time complexity is linear.
Space complexity: O(1)
Bubble sort is an in-place sorting algorithm, which means it uses a constant
amount of extra memory (for variables like loop counters, etc.), regardless
of the size of the input.
Bubble Sort compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the array is sorted.
Time Complexity
Worst Case: O(n^2) -This occurs when the input array is in reverse order. In each iteration of the outer loop, the inner loop will compare and potentially swap each of the remaining unsorted elements. This leads to approximately n(n-1)/2 operations, which is the order of O(n^2).
Average Case: O(n^2) - On average, bubble sort will still need to perform a quadratic number of operations. This is because, on average, it will still need to perform roughly half of the comparisons and swaps as in the worst-case scenario for any given random array.
Best Case: O(n) - This occurs when the input array is already sorted. In the best case (when an optimized version of bubble sort is used that terminates early if no swaps were made in a pass), only n-1 comparisons will be made and no swaps. Hence the best case time complexity is linear.
Space complexity: O(1)
Bubble sort is an in-place sorting algorithm, which means it uses a constant amount of extra memory (for variables like loop counters, etc.), regardless of the size of the input.