Sorting of array in C++

August 22, 2023

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.

Introduction to Arrays

Introduction to 2-D Arrays

Array Rotation

Reverse an array or string

Find pairs in array with given sum

1. Via Bubble Sort

Run

#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

Run

#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

Sorting of array in C++