#include <iostream>
#include <vector>
// Bubble Sort
void bubbleSort(std::vector<int>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
for (size_t j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
// Selection Sort
void selectionSort(std::vector<int>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
size_t minIdx = i;
for (size_t j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
std::swap(arr[i], arr[minIdx]);
}
}
// Insertion Sort
void insertionSort(std::vector<int>& arr) {
size_t n = arr.size();
for (size_t i = 1; i < n; ++i) {
int key = arr[i];
size_t j = i;
while (j > 0 && arr[j - 1] > key) {
arr[j] = arr[j - 1];
--j;
}
arr[j] = key;
}
}
// Merge Sort Helper Function
void merge(std::vector<int>& arr, int left, int mid, int right) {
std::vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left; i <= right; ++i) {
arr[i] = temp[i - left];
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Quick Sort Helper Function
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
std::vector<int> arrCopy = arr;
std::cout << "Original array: ";
printArray(arr);
std::cout << "Bubble Sort: ";
bubbleSort(arr);
printArray(arr);
arr = arrCopy;
std::cout << "Selection Sort: ";
selectionSort(arr);
printArray(arr);
arr = arrCopy;
std::cout << "Insertion Sort: ";
insertionSort(arr);
printArray(arr);
arr = arrCopy;
std::cout << "Merge Sort: ";
mergeSort(arr, 0, arr.size() - 1);
printArray(arr);
arr = arrCopy;
std::cout << "Quick Sort: ";
quickSort(arr, 0, arr.size() - 1);
printArray(arr);
return 0;
}
