Sorting Algorithms in C++

Sorting is a basic concept in computer programming that is important in optimizing performance, improving data organization, and simplifying algorithmic operations. In C++ programming, sorting algorithms are used to sort the data and are also used to enhance speed and user experience in real-time systems, too. The sorting algorithms also help beginners to understand the data structure and build applications. In this article, we will discuss what sorting is in C++, why sorting matters, sorting criteria, categories of sorting, types of sorting algorithms, sorting using the C++ library, and drawbacks of sorting algorithms in C++.

Table of Contents:

• What is Sorting in C++?
• Why Sorting is Important in C++?
• Sorting Criteria in C++
• Categories of Sorting in C++
• Types of Sorting Algorithms in C++
  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Quick Sort
  • Heap Sort
  • Merge Sort
• Sorting Using C++ Library
• Drawbacks of Sorting Algorithms in C++
• Conclusion

What is Sorting in C++?

Sorting is the process of arranging data in a specific order, either in ascending or descending order. It is a fundamental operation in C++ programming that is used to increase efficiency and optimization. Also, there are a number of sorting algorithms with their own features and complexities that are used in computer science and programming.

Why Sorting Matters in C++?

• Enhances Search Speed: It makes algorithms faster, such as binary search (O(log n)).
• Enhances Data Presentation: Makes tables, reports, and lists simpler to read and comprehend.
• Data Preparation for Additional Algorithms: A Sorted input is necessary for many algorithms (such as binary search trees and merges).
• Simplifies Duplicate Detection: Sorted data makes it possible to efficiently find duplicates through adjacent comparisons.
• Enhances Data Merging: It is much easier and faster to merge two sorted datasets.
• Improves User Experience: App and website usability is increased by sorting by popularity, date, or relevance.
• Increases Consistency: Sorted output helps with debugging and testing because it is predictable.

Sorting Criteria in C++

It is important to consider a few key criteria while sorting data that affect how the data is organized and how the sorting techniques behave with that data. Below are a few criteria that must be considered:

Categories of Sorting in C++

There are two categories of sorting in C++:

1. Internal sorting 
2. External sorting

Let’s discuss both categories briefly.

Internal Sorting

Internal sorting is a sorting category in which algorithms operate on data that fits completely in the main memory of the computer (RAM). Internal sorting is good for smaller to moderately sized data for accessing data faster. 

Examples: Quick sort, Heap sort, Bubble sort, Insertion sort, and Selection sort

External Sorting

External sorting is a sorting category that is good for very large datasets that require external memory. Algorithms under this category are slower due to the large and complex data.

Example: Merge sort

Here are a few differences between the sorting categories:

Types of Sorting Algorithms in C++

There are various types of sorting algorithms in C++. Let’s discuss each of the algorithms in brief with C++ examples.

1. Bubble Sort

Bubble sort is one of the simplest comparison-based sorting algorithms. In this sorting technique, at first two elements of an array are compared by checking if the first element is greater than the second element, and if it is so, then the elements are swapped. It works by repeatedly swapping elements in a similar way by moving to the next element, and the process repeats until the array is sorted.

Pseudocode:

procedure bubbleSort(arr[], n)
    for i from 0 to n-1
        for j from 0 to n-i-2
            if arr[j] > arr[j+1]
                swap arr[j] and arr[j+1]

Time and Space Complexity:

Example:

Output:

Explanation:

• Here, we have taken an array {64, 25, 12, 22, 11} which is sorted using the two nested for-loops. 
• The outer loop runs from index 0 to n-1, the inner loop runs from 0 to n-i-1, and in each pass, the adjacent elements arr[i] and arr[j+1] are compared and checked. 
• If arr[j] is greater than arr[j+1], then they are swapped, and in a similar way, the other elements are swapped. 
• The process is repeated until the array we have taken is sorted in ascending order, and then the sorted array {11, 12, 22, 25, 64} is printed to the console.

2. Selection Sort

Selection sort is a sorting algorithm in which the first element is assumed to be the smallest element, and then the remaining array is traversed with loops to find the actual smallest element. 

In this sorting technique, the array is divided into two halves: sorted and unsorted parts. The sorted subarray is on the left, and the unsorted subarray is on the right. The smallest element is picked from the unsorted part of the array and swapped with the unsorted element in the array, and this process is repeated until the whole array is sorted.

Pseudocode:

procedure selectionSort(arr[], n)
    for i from 0 to n-1
        minIndex = i
        for j from i+1 to n-1
            if arr[j] < arr[minIndex]
                minIndex = j
        swap arr[i] and arr[minIndex]

Time and Space Complexity:

Example:

Output:

Explanation:

• In this example, we have taken an unsorted array {29, 10, 14, 37, 13}. 
• In the first pass, we are assuming 29 is the smallest element, and then we check the other elements. So, here, 10 is smaller than 29, thus, we swap 29 and 10. Now, the array becomes {10, 29, 14, 37, 13}. 
• In the second pass, we assume 29 is the smallest again, now at index 1, and 14 is smaller, so it is swapped. Now, 13 is also smaller, and it becomes the new minimum, thus it is swapped too. Now, the array becomes {10, 13, 14, 37, 29}. 
• Now, the process is repeated similarly until the array is sorted, and then the sorted array {10, 13, 14, 29, 37} is printed to the console.

3. Insertion Sort

Insertion sort is an in-place, comparison-based, and stable sorting algorithm. In this sorting technique, the first element of the array is compared with the second element, and if it is smaller than it is swapped. This process is repeated until the entire array is sorted.

Pseudocode:

procedure insertionSort(arr[], n)
    for i from 1 to n-1
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key
            arr[j+1] = arr[j]
            j = j - 1
        arr[j+1] = key

Time and Space Complexity:

Example:

Output:

Explanation:

• In this example, we have taken an unsorted array {25, 17, 31, 13, 2}. 
• At first, we have taken the second element (17) and compared it with the first element (25), and since 17 is smaller, 25 is shifted to the right and 17 is inserted in its place. The array becomes {17, 25, 31, 13, 2}. 
• Now, we have moved to 31, which is greater than 25, so it is not replaced. The array becomes {17, 25, 31, 13, 2}. 
• Next, we have taken 13, compared it with 31, and since it is smaller than 31, 31 is shifted and 13 is inserted in its place. And 13 is also compared with 25 and 17 and gets replaced. The array becomes { 13, 17, 25, 31, 2}.
• Now, we have moved to 2, compared and shifted all elements one by one, and then 2 is inserted at the beginning of the array. Finally, the sorted array {2, 13, 17, 25, 31} is printed to the console.

4. Quick Sort

Quick sort is the most efficient and comparison-based sorting algorithm. This sorting algorithm uses a divide-and-conquer approach, in which the array is divided into two halves and then the array is sorted. 

In this sorting technique, a pivot element is selected that divides the array into two halves, such that all the elements less than the pivot are on the left and all elements greater than the pivot are on the right. After dividing the array, the same process is applied to the subarrays. The whole process is repeated until the entire array is sorted.

Pseudocode:

procedure quickSort(arr[], low, high)
    if low < high
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)

procedure partition(arr[], low, high)
    pivot = arr[high]
    i = low - 1
    for j from low to high - 1
        if arr[j] < pivot
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i+1] and arr[high]
    return i + 1

Time and Space Complexity:

Example:

Output:

Explanation:

• In this example, we have taken an array {33, 10, 55, 71, 29, 3}, and the pivot is 3. Now, since the pivot is 3, all the elements are on the right side, so 3 moves to the front, and then 33 becomes the pivot. 
• Now, since 33 is the pivot, the smaller elements are placed on the left and the greater elements are placed on the right. The array becomes {3, 10, 29, 31, 71, 55}.
• Now, we will take the subarrays {10, 29} and {71, 55}. Since the first subarray is already sorted, it is kept as it is, and 55 becomes the pivot for the second subarray. Since 71 is greater than 55, the subarray becomes {55, 71}.
• Now, finally, all the subarrays are merged, and the sorted array {3, 10, 29, 33, 55, 71} is printed to the console.

5. Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure means a max heap to extract the maximum element from the heap of the input data. It basically works in two main phases:

1. It builds a max heap from the input data or the array elements.
2. Now, it extracts the maximum element from the heap and places it at the end of the array. Then, reheapify the remaining elements, and repeat the process until the heap is empty.

Pseudocode:

procedure heapSort(arr[], n)
    // Build max heap
    for i from n/2 - 1 down to 0
        heapify(arr, n, i)

    // Extract elements from heap one by one
    for i from n-1 down to 0
        swap arr[0] and arr[i]
        heapify(arr, i, 0)

procedure heapify(arr[], n, i)
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]
        largest = left

    if right < n and arr[right] > arr[largest]
        largest = right

    if largest != i
        swap arr[i] and arr[largest]
        heapify(arr, n, largest)

Time and Space Complexity:

Example:

Output:

Explanation:

• In this example, we have taken the elements of the array and built a max heap to extract the maximum element to sort the array in ascending order. 
• Every extracted maximum element is placed at the end of the array, and the effective heap size is reduced. 
• This process is repeated until the heap is empty, and then the sorted array {5, 6, 7, 11, 12, 13} is printed to the console.

6. Merge Sort

Merge sort is a sorting algorithm that uses a divide-and-conquer approach to divide the array into two halves, sort the subarrays, and then merge the sorted halves as the final sorted array.

This sorting algorithm works in three steps:

1. It divides the array into two halves.
2. Sorts each half recursively.
3. Merges the sorted halves into a single sorted array.

Pseudocode:

procedure mergeSort(arr[], left, right)
    if left < right
        mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)

procedure merge(arr[], left, mid, right)
    n1 = mid - left + 1
    n2 = right - mid
    create arrays L[0..n1-1] and R[0..n2-1]

    for i from 0 to n1-1
        L[i] = arr[left + i]
    for j from 0 to n2-1
        R[j] = arr[mid + 1 + j]

    i = 0, j = 0, k = left
    while i < n1 and j < n2
        if L[i] <= R[j]
            arr[k] = L[i]
            i = i + 1
        else
            arr[k] = R[j]
            j = j + 1
        k = k + 1

    while i < n1
        arr[k] = L[i]
        i = i + 1
        k = k + 1

    while j < n2
        arr[k] = R[j]
        j = j + 1
        k = k + 1

Time and Space Complexity:

Example:

Output:

Explanation:

• In this example, we have taken an array {38, 27, 43, 3, 9, 82, 10} and divided the array into two halves, such as {38, 27, 43} and {3, 9, 82, 10}. 
• This process of dividing the array continues until all subarrays have only one element. After that, each subarray is merged in a manner such that {38} and {27} are merged to form {27, 38}, in the sorted ascending order. 
• Then, at last two larger subarrays are merged to produce the fully sorted array {3, 9, 10, 27, 38, 43, 82}, and it is printed to the console.

Sorting Using C++ Library

In C++, there is a built-in sorting function called std::sort(), which is defined in the <algorithm> header. An array can be sorted using this C++ library, too. 

Syntax:

std::sort(vec.begin(), vec.end());

For more information, you can check this table:

Example:

Output:

In this example, we have used the sort() function from the C++ Standard Library to sort an integer array {8, 4, 2, 9, 5} in ascending order by comparing the array elements from the start to the end of the array, and then the final sorted array {2, 4, 5, 8, 9} is printed to the console.

Drawbacks of Sorting Algorithms in C++

1. Slow on Large Data Sets: Simple sorting algorithms such as Bubble Sort or Selection Sort take a long time to work with large numbers of elements.
2. Uses More Memory: Sorting algorithms, such as Merge Sort, use extra space to perform their task, which affects performance if memory is limited.
3. May Change Order of Equal Items: The sorting algorithms, such as Quick Sort, will not retain the same order of equal items, and this may be important in certain programs.
4. Too Many Function Calls: Sorting algorithms that are recursive, such as Quick Sort, may create too many calls that can slow down the performance and cause problems with larger datasets.
5. Hard to Program: Some of these sorting algorithms are difficult to understand and program, thus making it difficult for beginners to use.
6. Not Good for Real-time Tasks: Sorting algorithms take time, and it usually isn’t the best task to perform when something should be done right away or in real-time.

Conclusion

Sorting is a basic principle of C++ that organizes data into sets of values, ultimately allowing that data to be sorted, searched, analyzed, or presented. It does not matter if your application is simple or if you have a large dataset to sort, knowing which sorting algorithm will be right for you is important: Bubble Sort if you want simplicity, Quick Sort if you want speed. By learning how sorting algorithms work and how to use them in order to write better and more optimized C++ programs, you can easily implement them.

Sorting Algorithms in C++ – FAQs