Selection Sort, Bubble Sort, Insertion Sort in C++

sorting_techniques.cpp

#include <iostream>
#include <vector>
using namespace std;

void printArray(vector<int> &arr) {
  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << "\t";
  }
}

// Selection Sort
// Select the one element and replace it with smallest element.
void selectionSort(vector<int> &arr, int n) {
  int min_index;

  for (int i = 0; i < n; i++) {
    min_index = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[min_index]) {
        min_index = j;
      }
    }
    if (min_index != i) {
      swap(arr[i], arr[min_index]);
    }
  }
}

// Bubble Sort
// repeatedly swapping the adjacent elements if they are in the wrong order.

void bubbleSort(vector<int> &arr, int n) {
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swapped = true;
        swap(arr[j], arr[j + 1]);
      }
    }

    if (swapped == false)
      break;
  }
}
// Insertion sort is a simple sorting algorithm that works by iteratively
// inserting each element of an unsorted list into its correct position in a
// sorted portion of the list.

void insertionSort(vector<int> &arr, int n) {
  for (int i = 0; i <= n - 1; i++) {
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      swap(arr[j], arr[j - 1]);
      j--;
    }
  }
}
// TIME COMPLEXITY: O(N^2) || BEST CASE: O(N)

int main() {
  cout << "Enter the size of the vector: ";
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++) {
    cout << "Enter the element for the " << i << " index:\t";
    cin >> arr[i];
  }
  cout << "\nBefore sorting the array:\n";
  printArray(arr);
  
  selectionSort(arr, n);
//   bubbleSort(arr, n);
//   insertionSort(arr, n);
  
  cout << "\nAfter sorting the array:\n";
  printArray(arr);
}