Bubble Sort

 Bubble sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing adjacent elements, and swapping them if they are in the wrong order. This process repeats until no more swaps are needed, which means the list is sorted. Despite its simplicity, bubble sort is inefficient for large datasets.

Here's a more detailed explanation of the bubble sort algorithm:

1. Initialization: The algorithm starts with the first element of the list.
2. Comparison and Swap: It compares the current element with the next element in the list. If the current element is greater than the next element, they are swapped.
3. Pass Through the List: The algorithm then moves to the next element and repeats the comparison and swap process until it reaches the end of the list. This completes one pass.
4. Repeat: The process is repeated for the entire list. After each pass, the largest element in the unsorted section of the list moves to its correct position at the end of the list.
5. Optimization: An optimized version of bubble sort checks if any swaps were made during a pass. If no swaps were made, the list is already sorted, and the algorithm can terminate early.
6. Worst-Case and Average Complexity: The time complexity of bubble sort in the worst and average case is O(n2)O(n^2)O(n2), where nnn is the number of elements in the list. This is because each element is compared with every other element.
7. Best-Case Complexity: The best-case time complexity is O(n)O(n)O(n), which occurs when the list is already sorted. The algorithm only needs to pass through the list once to confirm that it is sorted.
8. Space Complexity: Bubble sort has a space complexity of O(1)O(1)O(1) because it only requires a constant amount of additional memory space for the swapping process.

Example

Consider the following example to illustrate bubble sort:

Unsorted List: [5, 3, 8, 4, 2]

Pass 1:

• Compare 5 and 3, swap: [3, 5, 8, 4, 2]
• Compare 5 and 8, no swap: [3, 5, 8, 4, 2]
• Compare 8 and 4, swap: [3, 5, 4, 8, 2]
• Compare 8 and 2, swap: [3, 5, 4, 2, 8]

Pass 2:

• Compare 3 and 5, no swap: [3, 5, 4, 2, 8]
• Compare 5 and 4, swap: [3, 4, 5, 2, 8]
• Compare 5 and 2, swap: [3, 4, 2, 5, 8]
• Compare 5 and 8, no swap: [3, 4, 2, 5, 8]

Pass 3:

• Compare 3 and 4, no swap: [3, 4, 2, 5, 8]
• Compare 4 and 2, swap: [3, 2, 4, 5, 8]
• Compare 4 and 5, no swap: [3, 2, 4, 5, 8]
• Compare 5 and 8, no swap: [3, 2, 4, 5, 8]

Pass 4:

• Compare 3 and 2, swap: [2, 3, 4, 5, 8]
• Compare 3 and 4, no swap: [2, 3, 4, 5, 8]
• Compare 4 and 5, no swap: [2, 3, 4, 5, 8]
• Compare 5 and 8, no swap: [2, 3, 4, 5, 8]

Pass 5:

• Compare 2 and 3, no swap: [2, 3, 4, 5, 8]
• Compare 3 and 4, no swap: [2, 3, 4, 5, 8]
• Compare 4 and 5, no swap: [2, 3, 4, 5, 8]
• Compare 5 and 8, no swap: [2, 3, 4, 5, 8]

Sorted List: [2, 3, 4, 5, 8]

Key Points

• Stability: Bubble sort is a stable sort. This means that it maintains the relative order of records with equal keys.
• Adaptability: Although bubble sort is generally inefficient, its adaptability to nearly sorted lists makes it useful in specific scenarios where only a few elements are out of order.
• Simple Implementation: Its straightforward logic and easy implementation make bubble sort an educational tool for understanding the basics of sorting algorithms.

#include<iostream>

using namespace std;

class BubbleSort

{

int a[20],length,i,j;

public:

BubbleSort()

{

length=5;

}

void input_length()

{

cout<<"Enter length"<<endl;

cin>>length;

}

void input_array()

{

cout<<"Enter array elements"<<endl;

for(i=0;i<length;i++)

{

cin>>a[i];

}

}

void display_array()

{

for(i=0;i<length;i++)

{

cout<<a[i]<<" "<<endl;

}

}

void bubbleSort()

{

for(i=0;i<length;i++)

{

for(j=0;j<length-i-1;j++)

{

if(a[j]>a[j+1])

{

int temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

}

};

int main()

{

BubbleSort ob;

ob.input_length();

ob.input_array();

cout<<"Array elements before sorting"<<endl;

ob.display_array();

ob.bubbleSort();

cout<<"Array elements after sorting"<<endl;

ob.display_array();

return 0;

}

Bubble Sort Algorithm

Input

• A list of elements arrarrarr of length nnn

Output

• The sorted list arrarrarr in ascending order

Steps

1. Start:
• Initialize the list arrarrarr and determine its length nnn.
2. Outer Loop:
• For iii from 0 to n−1n-1n−1:
• This loop will ensure that all elements are checked and sorted.
3. Swapped Flag:
• Set a boolean variable swapped to false at the beginning of each iteration of the outer loop.
• This flag helps in optimizing the algorithm by stopping early if no elements were swapped in an entire pass.
4. Inner Loop:
• For jjj from 0 to n−i−2n-i-2n−i−2:
• This loop iterates through the list up to the unsorted portion.
5. Comparison and Swap:
• If arr[j]>arr[j+1]arr[j] > arr[j+1]arr[j]>arr[j+1]:
• Swap arr[j]arr[j]arr[j] and arr[j+1]arr[j+1]arr[j+1].
• Set swapped to true.
6. Early Termination:
• After the inner loop ends, check if swapped is still false:
• If true, break out of the outer loop since the list is already sorted.
7. End:
• Return the sorted list arrarrarr.

Pseudocode

function bubbleSort(arr):

n = length(arr)

for i from 0 to n-1:

swapped = false

for j from 0 to n-i-2:

if arr[j] > arr[j+1]:

swap(arr[j], arr[j+1])

swapped = true

if not swapped:

break

return arr

function swap(a, b):

temp = a

a = b

b = temp

Example in Python

Here's the bubble sort algorithm implemented in Python:

def bubble_sort(arr):

n = len(arr)

for i in range(n):

swapped = False

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

swapped = True

if not swapped:

break

return arr

# Example usage

arr = [5, 3, 8, 4, 2]

sorted_arr = bubble_sort(arr)

print(sorted_arr) # Output: [2, 3, 4, 5, 8]

Explanation

1. Outer Loop: Runs from 0 to n−1n-1n−1. After each pass, the next largest element is in its correct position.
2. Inner Loop: Runs from 0 to n−i−2n-i-2n−i−2. This loop compares each pair of adjacent elements and swaps them if they are in the wrong order.
3. Swapping: When a swap is made, it indicates that the list is not yet sorted.
4. Early Termination: If no swaps were made during an inner loop iteration, the list is already sorted, and the algorithm terminates early.
5. Return: The sorted list is returned at the end.

Bubble sort is straightforward to implement and understand, making it a useful algorithm for educational purposes despite its inefficiency for large datasets.