Code in (Java)
// Java program for implementation of Bubble Sort
import java.util.*;
class BubbleSort {
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
/* Prints the array */
void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method to test above
public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
int arr[] = { 5, 1, 4, 2, 8 };
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
Time Complexity
The above function always runs O(N2) time even if the array is sorted.
It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.
Time Complexity: O(N2)
Space Complexity
The Space Complexity of the Bubble Sort Algorithm Bubble sort requires only a fixed amount of extra space for the flag, i, and size variables.
As a result, the space complexity of bubble sort is O. (1).
Auxiliary Space: O(1)