Introduction
To sort array in C++ is a fundamental task that can be achieved using different algorithms and in this blog post, we will explore the most common sorting algorithms in C++, providing examples and their respective outputs. By the end of the guide, you will have a good understanding of how to effectively sort array in C++.
1) The Bubble Sort Algorithm
The Bubble Sort algorithm is a straightforward method to sort array in C++, although it may not be the most efficient option for handling large datasets. Its operation involves iterating through the list, checking neighboring elements, and swapping them if they are out of order. This process repeats until the entire array is sorted.
Example of Sort Array in C++ using Bubble Sort Algorithm
#include <iostream>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
std::cout << "Sorted array using Bubble Sort: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
Output:
Sorted array using Bubble Sort: 11 12 22 25 34 64 90 2) The Selection Sort Algorithm
The Selection Sort algorithm is a straightforward method to sort array in C++. It works by splitting the given array into two parts: the sorted sub array and the unsorted sub array. The algorithm consistently identifies the smallest element in the unsorted sub array and places it at the end of the sorted sub array.
Example of Sort Array in C++ using the Selection Sort Algorithm
#include <iostream>
void selectionSort(int arr[], int n) {
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() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
std::cout << "Sorted array using Selection Sort: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
Output:
Sorted array using Selection Sort: 11 12 22 25 34 64 903) The Insertion Sort Algorithm
The Insertion Sort algorithm is a straightforward method to sort array in C++ and gradually constructs the sorted array by adding one item at a time. While it may not be as efficient as other algorithms like quick sort, heap sort, or merge sort for handling large lists, Insertion Sort is often preferred in practical applications due to its simplicity of implementation and efficiency when dealing with small data sets.
Example of Sort Array in C++ using the Insertion Sort Algorithm
#include <iostream>
void insertionSort(int arr[], int n) {
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() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
std::cout << "Sorted array using Insertion Sort: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
Output:
Sorted array using Insertion Sort: 11 12 22 25 34 64 90 4) The Quick Sort Algorithm
The Quick Sort algorithm is not only widely used, but it is also highly efficient and operates in place. Its effectiveness lies in the fact that it selects a “pivot” element from the array and expertly divides the remaining elements into two sub-arrays based on whether they are smaller or larger than the pivot.
Example of Sort Array in C++ using the Quick Sort Algorithm
#include <iostream>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(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);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
std::cout << "Sorted array using Quick Sort: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
Output:
Sorted array using Quick Sort: 11 12 22 25 34 64 90 5) The Merge Sort Algorithm
Merge Sort is an efficient algorithm that follows the divide and conquers approach. It effectively breaks down the input array into smaller parts, sorts them individually, and finally merges them together to create a perfectly sorted array. This method is incredibly powerful in terms of its ability to handle large datasets with ease and precision.
Example of Sort Array in C++ using the Merge Sort Algorithm
#include <iostream>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
std::cout << "Sorted array using Merge Sort: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
Output:
Sorted array using Merge Sort: 11 12 22 25 34 64 90Conclusion
Sort array in C++ is a critical operation that finds application in a wide array of scenarios. In this blog post, we delved into various sorting algorithms, including Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, and Merge Sort. We provided examples of sort array in C++ alongside their corresponding outputs, shedding light on each algorithm’s unique characteristics. Each of these sorting techniques possesses distinct strengths and weaknesses, making the selection process dependent on specific project requirements, data size, and desired time complexity. Mastery of these sorting techniques is indispensable for any C++ programmer, equipping them with the necessary tools to efficiently handle and manipulate data in their applications.