Sorting Algorithms

Sorting is a fundamental operation in computer science and programming. It involves arranging a collection of elements in a specific order, such as ascending or descending. There are several sorting algorithms available, each with its own advantages and disadvantages.

1. Bubble Sort

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire collection is sorted. Although bubble sort is easy to implement, it is not very efficient and has a time complexity of O(n^2).

Here's an example implementation of bubble sort in C++:

1#include <iostream>
2#include <vector>
3
4void bubbleSort(std::vector<int>& arr) {
5    int n = arr.size();
6    for (int i = 0; i < n-1; ++i) {
7        for (int j = 0; j < n-i-1; ++j) {
8            if (arr[j] > arr[j+1]) {
9                std::swap(arr[j], arr[j+1]);
10            }
11        }
12    }
13}
14
15int main() {
16    std::vector<int> arr = {5, 2, 8, 1, 4};
17    bubbleSort(arr);
18
19    for (int num : arr) {
20        std::cout << num << " ";
21    }
22
23    return 0;
24}

2. Selection Sort

Selection sort works by repeatedly finding the minimum element from the unsorted portion of the collection and placing it at the beginning. This process is repeated until the entire collection is sorted. Selection sort also has a time complexity of O(n^2) but performs fewer swaps compared to bubble sort.

Here's an example implementation of selection sort in C++:

1#include <iostream>
2#include <vector>
3
4void selectionSort(std::vector<int>& arr) {
5    int n = arr.size();
6    for (int i = 0; i < n-1; ++i) {
7        int minIndex = i;
8        for (int j = i+1; j < n; ++j) {
9            if (arr[j] < arr[minIndex]) {
10                minIndex = j;
11            }
12        }
13        std::swap(arr[i], arr[minIndex]);
14    }
15}
16
17int main() {
18    std::vector<int> arr = {5, 2, 8, 1, 4};
19    selectionSort(arr);
20
21    for (int num : arr) {
22        std::cout << num << " ";
23    }
24
25    return 0;
26}

3. Insertion Sort

Insertion sort works by dividing the collection into sorted and unsorted portions. It iterates over each unsorted element and inserts it into the correct position in the sorted portion. Insertion sort has a time complexity of O(n^2), but it performs well for small collections or nearly sorted collections.

Here's an example implementation of insertion sort in C++:

1#include <iostream>
2#include <vector>
3
4void insertionSort(std::vector<int>& arr) {
5    int n = arr.size();
6    for (int i = 1; i < n; ++i) {
7        int key = arr[i];
8        int j = i - 1;
9        while (j >= 0 && arr[j] > key) {
10            arr[j+1] = arr[j];
11            --j;
12        }
13        arr[j+1] = key;
14    }
15}
16
17int main() {
18    std::vector<int> arr = {5, 2, 8, 1, 4};
19    insertionSort(arr);
20
21    for (int num : arr) {
22        std::cout << num << " ";
23    }
24
25    return 0;
26}

These are just a few examples of sorting algorithms in C++. By exploring different sorting algorithms, you can gain a deeper understanding of their implementations and choose the most appropriate one for specific scenarios. Remember to consider factors like time complexity, space complexity, and stability when selecting a sorting algorithm.