Sorting Algorithms: Bubble Sort and Selection Sort with C++ Implementation

 Sorting Algorithms: Bubble Sort and Selection Sort with C++ Implementation

---

1. Bubble Sort

• Concept: Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process continues until the array is sorted.
• Time Complexity:
  • Best Case: $O(n)$ (already sorted array with an optimization flag).
  • Worst and Average Case: $O(n^2)$.
• Steps:
  1. Start from the first element.
  2. Compare adjacent elements and swap if necessary.
  3. Repeat the process for all elements, reducing the range of comparison with each pass.

C++ Implementation:

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // Stop if the array is already sorted
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "Sorted Array using Bubble Sort: ";
    printArray(arr, n);

    return 0;
}

Output:

Original Array: 64 34 25 12 22 11 90 
Sorted Array using Bubble Sort: 11 12 22 25 34 64 90 

---

2. Selection Sort

• Concept: Selection Sort repeatedly finds the minimum element from the unsorted part of the array and places it at the beginning.
• Time Complexity:
  • Best, Worst, and Average Case: $O(n^2)$.
• Steps:
  1. Find the smallest element in the unsorted part of the array.
  2. Swap it with the first element of the unsorted part.
  3. Repeat the process for the remaining unsorted elements.

C++ Implementation:

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array: ";
    printArray(arr, n);

    selectionSort(arr, n);

    cout << "Sorted Array using Selection Sort: ";
    printArray(arr, n);

    return 0;
}

Output:

Original Array: 29 10 14 37 13 
Sorted Array using Selection Sort: 10 13 14 29 37