Bubble Sort

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating that the list is sorted. It is called "bubble sort" because smaller elements "bubble" to the top of the list as the algorithm iterates through it.

Here's a step-by-step description of the bubble sort algorithm along with a real-time example:

Algorithm Description:

1.Start at the beginning of the list.

2.Compare the first two elements. If the first element is larger than the second element, swap them.

3.Move to the next pair of elements (i.e., the second and third elements), and repeat step 2. Continue this process until you reach the end of the list. After this pass, the largest element will have "bubbled up" to the end of the list.

4.Repeat steps 1-3 for the remaining elements (excluding the last one, which is already in its correct position after the first pass).

5.Continue this process, reducing the number of elements to be compared in each pass by one, until no swaps are made in a complete pass through the list. This indicates that the list is sorted.

Example:

Let's use a real-time example to demonstrate how bubble sort works. Consider the following unsorted list of integers:

Original List: [5, 2, 9, 1, 5, 6]

Now, we'll go through each pass of the bubble sort algorithm:

Pass 1: (Comparing and swapping adjacent elements)Compare 5 and 2. Swap them since 5 > 2. List after the first comparison: [2, 5, 9, 1, 5, 6]

Compare 5 and 9. No swap needed.
Compare 9 and 1. Swap them since 9 > 1. List after the second comparison: [2, 5, 1, 9, 5, 6]
Compare 9 and 5. Swap them since 9 > 5. List after the third comparison: [2, 5, 1, 5, 9, 6]
Compare 9 and 6. Swap them since 9 > 6. List after the fourth comparison: [2, 5, 1, 5, 6, 9]

After Pass 1, the largest element (9) has moved to the end of the list.

Pass 2: (Continuing with the remaining elements)Compare 2 and 5. No swap needed.Compare 5 and 1. Swap them since 5 > 1. List after the second pass: [2, 1, 5, 5, 6, 9]

After Pass 2, the second largest element (5) has moved to the second last position.

Pass 3:Compare 2 and 1. Swap them since 2 > 1. List after the third pass: [1, 2, 5, 5, 6, 9]

After Pass 3, the next largest element (2) has moved to the third last position.

Pass 4:No swaps are needed in this pass since all elements are in their correct positions.

The algorithm terminates after Pass 4 because no swaps were made in this pass, indicating that the list is now sorted.

Sorted List: [1, 2, 5, 5, 6, 9]

Pseudo Code

procedure bubbleSort(arr: array of integers, n: integer)

    swapped = true

    while swapped is true

        swapped = false

        for i from 0 to n - 2

            if arr[i] > arr[i + 1]

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

                swapped = true

    end procedure

Time Complexity:

The time complexity of the Bubble Sort algorithm is O(n^2) in the worst and average cases, and O(n) in the best case.

Worst Case: In the worst case scenario, the input list is in reverse order, and you need to make n-1 passes through the list. In each pass, you compare and potentially swap n-1 elements. So, the total number of comparisons and swaps is approximately (n-1) * (n-1), which is O(n^2).

Average Case: On average, you'll also make O(n^2) comparisons and swaps, making it an O(n^2) algorithm.

Best Case: The best-case scenario occurs when the input list is already sorted. In this case, you still need to make n-1 passes through the list to confirm that no swaps are needed. However, in each pass, no swaps will occur. So, the algorithm performs n-1 comparisons in the best case, resulting in an O(n) time complexity.

Bubble Sort is not efficient for large lists due to its quadratic time complexity. There are more efficient sorting algorithms like Quick Sort and Merge Sort with better average and worst-case time complexities.

Space Complexity:

The space complexity of the Bubble Sort algorithm is O(1), which means it uses a constant amount of additional memory regardless of the size of the input list. Bubble Sort primarily swaps elements in-place and doesn't require additional data structures or memory allocation proportional to the input size.

In summary, Bubble Sort is simple to understand and implement but is not suitable for sorting large lists due to its quadratic time complexity. Its main advantage is its minimal space usage, making it an in-place sorting algorithm.

C- program BubbleSort

/*******************************************************************************/

#include<stdio.h>

void swap(int *x, int *y) {

    int temp = *x;

    *x = *y;

    *y = temp;

}

void bubbleSort(int arr[], int n) {

    int swapped = 1;

    while (swapped) {

        swapped = 0;

        for (int i = 0; i < n - 1; i++) {

            if (arr[i] > arr[i + 1]) {

                swap(&arr[i], &arr[i + 1]);

                swapped = 1;

            }

        }

    }

}

int main(){

int size,i;

printf("Enter size of the array: ");

scanf("%d",&size);

int arr[size];

printf("Enter %d elements: ",size);

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

scanf("%d",&arr[i]);

bubbleSort(arr,size);

printf("Sorted elements: ");

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

printf(" %d",arr[i]);

return 0;

}