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, such as search engines, e-commerce platforms, and financial systems. The sorting algorithms in C++ 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 STL in C++, and drawbacks of sorting algorithms in C++.

Table of Contents:

• What is Sorting in C++?
• Why is Sorting Important in C++ Programming?
• 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++
• Stable vs Unstable Sorting Algorithms in C++
• Real-World Use Cases of Sorting in C++
• Conclusion

What is Sorting in C++?

Sorting in C++ 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, and data organization in C++. Also, there are a number of sorting algorithms in C++, such as Bubble Sort, Quick Sort, Merge Sort, Heap Sort, and Insertion Sort, with their own features and complexities that are used in computer science and programming. This is useful for developers to know how to create fast, optimized, and scalable programs.

Why is Sorting Important in C++ Programming?

Here are the reasons that will help you understand the importance of sorting in programming:

• Enhances Search Speed: It makes algorithms faster, such as binary search (O(log n)).
• Enhances Data Presentation: Sorting in C++ 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: Sorting in C++ is much easier and faster to merge two sorted datasets.
• Improves User Experience: App and website usability is increased by sorting in C++ 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 basic sorting techniques behave with that data. Below are a few criteria for sorting in C++ that must be considered:

Categories of Sorting in C++

There are two types of sorting in C++:

1. Internal sorting 
2. External sorting

Let’s discuss both categories of sorting in C++ briefly.

1. 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). This type of sorting in C++ is good for smaller to moderately sized data for accessing data faster. 

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

2. External Sorting

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

Example: Merge sort

Here is a comparison table of internal vs external sorting that shows 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 sorting algorithms with examples in C++ in brief.

1. Bubble Sort

Bubble sort is one of the simplest comparison-based sorting algorithms in C++. In this basic 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 of Bubble Sort in C++:

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 of Selection Sort in C++:

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 of Insertion Sort in C++:

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 of Quick Sort in C++:

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 of Heap Sort in C++:

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 of Merge Sort in C++:

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 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

For sorting 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 STL in C++, too. This is the preferred method of sorting in C++ for most sorting tasks.

Syntax:

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

For more information on sorting in C++ with the library, you can check this table:

C++ std::sort() 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.

Note: You can also use a C++ sort comparator function to define custom sorting logic. But for sorting vectors in C++, this is the most common approach.

Drawbacks of Sorting Algorithms in C++

1. Slow on Large Data Sets: Simple sorting algorithms in C++, such as Bubble Sort or Selection Sort, take a long time to work with large numbers of elements.
2. Uses More Memory: C++ 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 in C++, 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: C++ 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 in C++ 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.

Stable vs Unstable Sorting Algorithms in C++

Here is a comparison table of Stable vs Unstable sorting algorithms in C++:

Real-World Use Cases of Sorting in C++

• Databases & Search Engines: Sorting plays an important role in query optimization, indexing, and ranking search results. When you enter a keyword in Google, then billions of results are sorted before they are shown to you, based on the relevance of the given keywords.
• E-commerce & Online Platforms: A great example of sorting would be Amazon or Flipkart, which sort their products as they are very likely in the millions, by price, rating, or popularity, based on efficient sorting algorithms.
• Operating Systems & File Management: Multilevel sorting in C++ will help with scheduling processes, managing multiple processes, and then file sorting.
• Gaming & Graphics: Sorting is part of rendering pipelines to ensure proper 3D rendering, in which you sort the objects by depth, and it is also common in leaderboard rankings.
• Financial Systems: Banks, stock markets, and fintech apps sort data, i.e., transactions, prices, and market data, in real-time so that they can be used for analysis.

Conclusion

Sorting in C++ is a basic principle that organizes data into sets of values, ultimately making that data easier to sort, search, analyze, and present. It does not matter if your application is simple or if you have a large dataset to sort; knowing which sorting algorithm in C++ will be right for you is important: Bubble Sort if you want simplicity, Quick Sort if you want speed. By learning how C++ 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