Sorting algorithms in C++ are fundamental techniques used to arrange elements in a specific order, typically ascending or descending. Choosing the right sorting algorithm depends on factors such as the size of the dataset, the distribution of data values, and whether the data is partially sorted or not. Here's an overview of some common sorting algorithms and their implementations in C++:
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process repeats until the list is sorted.
#include
#include
void bubbleSort(std::vector& arr) {
int n = arr.size();
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]) {
std::swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) {
break; // If no elements were swapped, array is already sorted
}
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(nums);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Selection sort divides the list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the first unsorted element.
#include
#include
void selectionSort(std::vector& arr) {
int n = arr.size();
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;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
selectionSort(nums);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Insertion sort builds the final sorted array one element at a time. It takes each element from the unsorted part and inserts it into its correct position in the sorted part.
#include
#include
void insertionSort(std::vector& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
insertionSort(nums);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Merge sort is a divide and conquer algorithm that divides the array into two halves, recursively sorts each half, and then merges the sorted halves.
#include
#include
void merge(std::vector& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector L(n1), R(n2);
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
void mergeSort(std::vector& 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);
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
mergeSort(nums, 0, nums.size() - 1);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Quick sort is another divide and conquer algorithm that picks an element as a pivot and partitions the array around the pivot. It is more efficient than merge sort for smaller datasets.
#include
#include
int partition(std::vector& 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& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
quickSort(nums, 0, nums.size() - 1);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It first builds a max-heap (or min-heap for descending order), then repeatedly extracts the root element to obtain a sorted array.
#include
#include
void heapify(std::vector& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector& arr) {
int n = arr.size();
// Build max heap
for (int i = n / 2 - 1; i >= 0; --i) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (int i = n - 1; i > 0; --i) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
heapSort(nums);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Counting sort is a non-comparison based sorting algorithm suitable for sorting integers when the range of elements is known beforehand. It counts the occurrences of each element and then places them in order.
#include
#include
void countingSort(std::vector& arr) {
int max = *std::max_element(arr.begin(), arr.end());
int min = *std::min_element(arr.begin(), arr.end());
int range = max - min + 1;
std::vector count(range), output(arr.size());
for (int i = 0; i < arr.size(); ++i) {
count[arr[i] - min]++;
}
for (int i = 1; i < range; ++i) {
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; --i) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.size(); ++i) {
arr[i] = output[i];
}
}
int main() {
std::vector nums = {64, 34, 25, 12, 22, 11, 90};
countingSort(nums);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Radix sort sorts integers by processing individual digits. It sorts numbers by processing individual digits starting from the least significant digit to the most significant digit.
#include
#include
void countSort(std::vector& arr, int exp) {
int n = arr.size();
std::vector output(n), count(10, 0);
for (int i = 0; i < n; ++i) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; ++i) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; ++i) {
arr[i] = output[i];
}
}
void radixSort(std::vector& arr) {
int max = *std::max_element(arr.begin(), arr.end());
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
int main() {
std::vector nums = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(nums);
std::cout << "Sorted array: ";
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}