Data Structures and Algorithms, IT Technology

A Guide to Sorting Algorithms in the C++ Standard Template Library (STL)

Posted on by Thao Nguyen

Sort is one of the most basic functions applied to data. This means that the data is arranged in a specific way, which can be increased or decreased. There is a built-in function in C++ STL called sort().

This function uses IntroSort internally. In more detail, it is implemented using a mix of QuickSort, HeapSort, and InsertionSort. By default, it uses QuickSort, but if QuickSort does unfair partitioning and takes longer than N*logN, it switches to HeapSort, and when the array size becomes very small, it switches to InsertionSort.

The archetypes of the sort are:

sort(startaddress, endaddress)

startaddress: the address of the first 
              element of the array
endaddress: the address of the next 
            contiguous location of the 
            last element of the array.
So actually sort() sorts in the 
range of [startaddress, endaddress)

CPP

// C++ progrma to sort an array
#include <algorithm>
#include <iostream>
 
using namespace std;
 
void show( int a[], int array_size)
{
     for ( int i = 0; i < array_size; ++i)
         cout << a[i] << " " ;
}
 
// Driver code
int main()
{
     int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
   
     // size of the array
     int asize = sizeof (a) / sizeof (a[0]);
     cout << "The array before sorting is : \n" ;
   
     // print the array
     show(a, asize);
 
       // sort the array
     sort(a, a + asize);
 
     cout << "\n\nThe array after sorting is :\n" ;
   
     // print the array after sorting
     show(a, asize);
 
     return 0;
}

The output is as follows

The array before sorting is : 
1 5 8 9 6 7 3 4 2 0 

The array after sorting is :
0 1 2 3 4 5 6 7 8 9

See std::sort() for more details.

Considered one of the most sought-after skills in the industry, we have our own coding foundation, C++ STL, to train and master these concepts through an intense problem-solving process.

Thao Nguyen