Bubble Sort

Bubble Sort in C

Introduction:

Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Algorithm:

1. Start:

   • Begin with the first element (index 0) and compare it with the next element.

2. Compare and Swap:

   • If the current element is greater than the next element, swap them.
   • Move to the next pair of elements.

3. Pass-Through the List:

   • Repeat the above steps for each pair of adjacent elements in the list.

4. End of Pass:

   • After one pass, the largest element is guaranteed to be at the end of the list.

5. Repeat:

   • Repeat the process for the remaining elements, excluding the last one after each pass.

6. Termination:

   • The algorithm terminates when no more swaps are needed, indicating that the list is sorted.

Original Array: 64 34 25 12 22 11 90 Pass 1: 64 34 25 12 22 11 90 // Compare 64 and 34, swap 34 64 25 12 22 11 90 // Compare 64 and 25, swap 34 25 64 12 22 11 90 // Compare 64 and 12, swap 34 25 12 64 22 11 90 // Compare 64 and 22, swap 34 25 12 22 64 11 90 // Compare 64 and 11, swap 34 25 12 22 11 64 90 // Compare 64 and 90, no swap Pass 2: 34 25 12 22 11 64 90 // Compare 34 and 25, swap 25 34 12 22 11 64 90 // Compare 34 and 12, swap 25 12 34 22 11 64 90 // Compare 34 and 22, swap 25 12 22 34 11 64 90 // Compare 34 and 11, swap 25 12 22 11 34 64 90 // Compare 34 and 64, no swap Pass 3: 25 12 22 11 34 64 90 // Compare 25 and 12, swap 12 25 22 11 34 64 90 // Compare 25 and 22, swap 12 22 25 11 34 64 90 // Compare 25 and 11, swap 12 22 11 25 34 64 90 // Compare 25 and 34, no swap Pass 4: 12 22 11 25 34 64 90 // Compare 12 and 22, no swap Pass 5: 12 11 22 25 34 64 90 // Compare 12 and 11, swap Sorted Array: 11 12 22 25 34 64 90 C Code Example:

#include <stdio.h> void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { // Compare adjacent elements if (arr[j] > arr[j+1]) { // Swap if they are in the wrong order int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); // Perform Bubble Sort bubbleSort(arr, n); // Display sorted array printf("Sorted array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }

Time Complexity:

• Bubble Sort has a worst-case and average-case time complexity of O(n^2) and a best-case time complexity of O(n) when the list is already sorted.

Space Complexity:

• Bubble Sort has a space complexity of O(1) as it only requires a constant amount of additional memory space.

Advantages and Disadvantages:

• Advantages:

  • Simple implementation.
  • Minimal memory usage.

• Disadvantages:

  • Inefficient for large datasets.
  • Quadratic time complexity.

Conclusion:

Bubble Sort is a basic sorting algorithm that is easy to understand but is not the most efficient for large datasets. It serves as a good introduction to sorting algorithms.

Feel free to customize and expand upon this outline based on your class requirements and the depth of information you want to cover.