Bubble Sort

Bubble sort is a simple sorting algorithm in which adjacent elements are compared to each other and swapped if the elements are not in intended order. It is a comparison based algorithm. This algorithm is not suitable for large data because of its not so good worst and average case time complexity O(n²), n is the number of elements.

Illustration:

Algorithm:

for all elements in list

    for adjacent elements of unsorted portion of list

        if leftElement > rightElement

            swap the elements

Time Complexity:

• Worst Case: O(n²)
• Average Case: O(n²)
• Best Case: O(n)

Space Complexity: O(1)

Program for Bubble Sort:

Output: