Sorting of array in C++
Sorting of Array in C++ Language
On this page, we will look into a coding question where we will learn how to sort the array in the C++ programming language. There are many sorting techniques to sort the array-like quick sort, merge sort, bubble sort, and insertion sort them is scripted below.
Here on this page, we are going to discuss the selection for sorting an array in C++.
Algorithm :
- Take the size of the array from the user.
- Declare an array of given input size.
- Take the input of all elements of the array.
- Now run a for loop from 0 to size-1.
- And for every element check it from all the next elements to it. If the element is greater than swap that number.
- In this way the array will get sorted in ascending order.
1. Via Bubble Sort
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cout<<"Enter the size of array: "; cin>>n;
int a[n];
cout<<"\nEnter the elements: ";
for(int i=0; i<n; i++) cin>>a[i];
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++) { if(a[i]>a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
cout<<"\nArray after swapping: ";
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
return 0;
}Output:
Enter the size of array: 5
Enter the elements: 1 3 2 5 4
Array after swapping: 1 2 3 4 5
2. Via Insertion Sort
#include
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;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
printArray(arr, n);
insertionSort(arr, n);
std::cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Original array: 64 25 12 22 11 Sorted array: 11 12 22 25 64
- The insertionSort function that takes an array arr and its size n. It iterates through the array, starting from the second element (index 1), and compares each element with the elements before it. If an element is smaller, it shifts the larger elements to the right until it finds the correct position to insert the current element.
- The printArray function is used to display the elements of the array. In the main function, we initialize an array, print the original array, call the insertionSort function to sort the array, and then print the sorted array.
3. Via Merge Sort
Run
#include < iostream>
// Merge two sorted subarrays into a single sorted subarray
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
int i = 0; // Index for the left subarray
int j = 0; // Index for the right subarray
int k = 0; // Index for the merged array
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
}
else {
arr[k] = right[j];
j++;
}
k++;
}
// Copy the remaining elements of the left subarray, if any
while (i < leftSize) {
arr[k] = left[i];
i++;
k++;
}
// Copy the remaining elements of the right subarray, if any
while (j < rightSize) {
arr[k] = right[j];
j++;
k++;
}
}
// Merge sort implementation
void mergeSort(int arr[], int size) {
if (size <= 1)
return;
int mid = size / 2;
// Create left and right subarrays
int left[mid];
int right[size - mid];
// Copy data to left and right subarrays
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
// Recursively sort the left and right subarrays
mergeSort(left, mid);
mergeSort(right, size - mid);
// Merge the sorted subarrays
merge(arr, left, mid, right, size - mid);
}
// Print the elements of an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {
99,
78,
88,
25,
26
};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
printArray(arr, size);
mergeSort(arr, size);
std::cout << "Sorted array: ";
printArray(arr, size);
return 0;
}
Output:
Original array: 99 78 88 25 26 Sorted array: 25 26 78 88 99
- The mergeSort function is the implementation of the merge sort algorithm. It recursively divides the array into two halves until the base case of size 1 is reached. It then merges the sorted subarrays using the merge function.
- The printArray function is used to display the elements of the array. In the main function, we initialize an array, print the original array, call the mergeSort function to sort the array, and then print the sorted array.
4. Via Quick Sort
Run
#include <iostream>
// Function to swap two elements
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Partition the array and return the pivot index
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose the rightmost element as the pivot
int i = low - 1; // Index of the smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1; // Return the pivot index
}
// Quick sort implementation
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
// Recursively sort the left and right subarrays
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// Print the elements of an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {55, 65, 32, 12, 19};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
printArray(arr, size);
quickSort(arr, 0, size - 1);
std::cout << "Sorted array: ";
printArray(arr, size);
return 0;
}
Output:
Original array: 55 65 32 12 19 Sorted array: 12 19 32 55 65
- The swap function to swap two elements in the array. The partition function chooses the rightmost element as the pivot and partitions the array into two subarrays – elements smaller than the pivot and elements greater than the pivot. It returns the index of the pivot element.
- The quickSort function is the implementation of the quick sort algorithm. It recursively selects a pivot, partitions the array, and then recursively sorts the left and right subarrays.
- The printArray function is used to display the elements of the array. In the main function, we initialize an array, print the original array, call the quickSort function to sort the array, and then print the sorted array.
4. Via Heap Sort
Run
#include <iostream>
// Function to heapify a subtree rooted at index i
void heapify(int arr[], int size, int rootIndex) {
int largest = rootIndex; // Assume the root as the largest element
int leftChild = 2 * rootIndex + 1; // Left child index
int rightChild = 2 * rootIndex + 2; // Right child index
// If the left child is larger than the root
if (leftChild < size && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
// If the right child is larger than the largest so far
if (rightChild < size && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
// If the largest element is not the root
if (largest != rootIndex) {
std::swap(arr[rootIndex], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, size, largest);
}
}
// Heap sort implementation
void heapSort(int arr[], int size) {
// Build a max-heap
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(arr, size, i);
}
// Extract elements from the heap one by one
for (int i = size - 1; i > 0; i--) {
std::swap(arr[0], arr[i]); // Move current root to the end
heapify(arr, i, 0); // Reduce the heap size and heapify the root
}
}
// Print the elements of an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
printArray(arr, size);
heapSort(arr, size);
std::cout << "Sorted array: ";
printArray(arr, size);
return 0;
}
Output:
Original array: 76 90 73 56 32 Sorted array: 32 56 73 76 90
- The heapify function to heapify a subtree rooted at index rootIndex. It compares the root element with its children and swaps them if necessary to maintain the max-heap property.
- The heapSort function is the implementation of the heap sort algorithm. It builds a max-heap from the array, then repeatedly extracts the maximum element (root) and performs heapify to maintain the max-heap property.
- The printArray function is used to display the elements of the array. In the main function, we initialize an array, print the original array, call the heapSort function to sort the array, and then print the sorted array.
5. Via Count Sort
Run
#include <iostream>
#include <algorithm>
// Get the maximum element from the array
int getMax(int arr[], int size) {
int max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Counting sort for a specific digit
void countingSort(int arr[], int size, int exp) {
const int RADIX = 10;
int output[size];
int count[RADIX] = {0};
// Count the occurrences of each digit
for (int i = 0; i < size; i++) {
count[(arr[i] / exp) % RADIX]++;
}
// Calculate the cumulative count
for (int i = 1; i < RADIX; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = size - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % RADIX] - 1] = arr[i];
count[(arr[i] / exp) % RADIX]--;
}
// Copy the output array to the original array
for (int i = 0; i < size; i++) {
arr[i] = output[i];
}
}
// Radix sort implementation
void radixSort(int arr[], int size) {
int max = getMax(arr, size);
// Perform counting sort for each digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, size, exp);
}
}
// Print the elements of an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {76, 90, 73, 56, 32};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
printArray(arr, size);
radixSort(arr, size);
std::cout << "Sorted array: ";
printArray(arr, size);
return 0;
}
Output:
Original array: 64 25 12 22 11 Sorted array: 11 12 22 25 64
- The getMax function to get the maximum element from the array. The countingSort function performs counting sort for a specific digit by counting the occurrences of each digit, calculating the cumulative count, and building the output array.
- The radixSort function is the implementation of the radix sort algorithm. It gets the maximum element from the array, then performs counting sort for each digit from the least significant digit to the most significant digit.
- The printArray function is used to display the elements of the array. In the main function, we initialize an array, print the original array, call the radixSort function to sort the array, and then print the sorted array.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment