Comparing sort(), partial_sort() and nth_element() sort() in C++ STL

In this post, we will be discussing what are the differences between Sort, Partial Sort, and nth_element Sort in C++.

sort in C++

This is function provided in C++ STL, which sort the given array in ascending order by default. It takes O(NlogN) time to sort an array.

//auhtor @Nishant

#include<bits/stdc++.h>
using namespace std;

int main(){
    // Given vector of elements
    vector<int>arr{1, 6, 4, 5, 2, 3};
    int n = arr.size();

    // STL function to sort the array
    sort(array.begin(), array.end());

    // Printing vector after sorting
    cout << "After sorting: ";
    for(int i = 0; i < n; i++){
        cout << arr.at(i) << " ";
    }
    return 0;
}
After sorting: 1 2 3 4 5 6

partial_sort in C++

Sometimes there comes a situation wherein you only want a part of an array to be sorted not the entire array, for such cases STL in C++ has a function called Partial_sort().

It reorders the array elements in the range [first, last), in such a way that all the elements occurring before a specific element are sorted in ascending order(by default) and all the elements after that are left as it is.

//auhtor @Nishant

#include <bits/stdc++.h>
using namespace std;

int main(){
    // Given vector of elements
    vector<int> arr{2, 4, 6, 1, 3, 7, 8, 5};
    int n = arr.size();
    
    // STL function partial_sort to sort first 5 elements
    partial_sort(arr.begin(), arr.begin() + 5, arr.end());
    
    // Printing vector after sorting
    cout << "After sorting: ";
    for(int i : arr){
        cout << i << " ";
    }
    return 0;
}
After sorting: 1 2 3 4 5 7 8 6

partial_sort is relatively faster than sort(), if M is smaller than N, where N is the no. of elements in the given array and m is the no. of elements to be sorted beginning from the start.
partial_sort has a time complexity of O(NlogM)

nth_element

Rearranges the array elements in the range [first, last), in such a way that the element at the nth position is the element that would be in that position in sorted order.
The other elements are left as it is, except that all the elements occurring before that element are smaller than it and all the elements occurring after the nth element are greater than it.

//auhtor @Nishant

#include <bits/stdc++.h>
using namespace std;

int main(){
    // Given vector of elements
    vector<int> arr{6, 7, 23, 5, 13, 10, 2};
    
    // Using nth_element with n as 3
    nth_element(arr.begin(), arr.begin() + 3, arr.end());
    
    // as n is 3 so 3rd element should be sorted
    cout << "After sorting: ";
    for(int i : arr){
        cout << i << " ";
    }
    return 0;
}
After sorting: 5 2 6 7 13 10 23

It is asymptomatically the fastest algorithm. It gives better results for larger M.

Leave a Reply

Your email address will not be published. Required fields are marked *