Sorting Algorithms I 📚

Agenda

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Count Sort
5. Radix Sort

1. Bubble Sort 🌀

• The basic idea of Bubble Sort is to swap two adjacent elements if they are in the wrong order.
• This process is repeated for N iterations, and for each iteration, the array is checked and swaps are made where necessary.
• Time Complexity: O(n²)

Time Complexity: O(n²)

void bubbleSort(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size() - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

2. Selection Sort 🧳

• The basic idea of Selection Sort is to find the minimum element and swap it with the current position. This process repeats for every element in the array.
• For each iteration, the algorithm selects the smallest element from the unsorted part of the array and places it at the beginning.
• Time Complexity: O(n²)

Time Complexity: O(n²)

void selectionSort(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}