In the C++ programming language, the list container is an essential part of the Standard Template Library (STL). The list container is implemented as a doubly linked list. It is very useful when elements must be inserted and removed from either end or from an arbitrary position.
In C++ , the list sort is a built-in member function of the list container. It is commonly utilized to arrange or sort the elements of a given list in increasing order (ascending order). It does not involve any construction or destruction of elements. Elements are only moved within the container. It is a member function because the linked list cannot provide random access iterators in C++.
Syntax
It has the following syntax in C++.
void sort();
In this syntax,
- Parameter: It does not contain any parameter.
- Return value: It does not return any value.
C++ Simple List Sort function Example
Let us take an example to demonstrate the list sort function in C++.
Example
#include <iostream>
#include<list>
using namespace std; //using standard namespace
intmain() //main function
{
list<int> li={6, 4, 10, 2, 4, 1};
list<int>:: iterator itr;
cout<<"Elements of the list are:";
for(itr=li.begin();itr!=li.end();++itr)
std::cout<< *itr<<" ";
li.sort();
cout<<'\n';
cout<<"Sorted elements are:";
for(itr=li.begin();itr!=li.end();++itr)
std::cout<< *itr<<" ";
return 0;
}
Output:
Elements of the list are: 6 4 10 2 4 1
Sorted elements are: 1 2 4 4 6 10
Explanation:
In this example, we have created an integer list named li that is initialized with the elements {6, 4, 10, 2, 4, 1}. After that, we use the sort function that sorts the elements in ascending order. At last, it displays the sorted list of a given list, and its output is 1 2 4 4 6 10.
C++ Example to Sort a List of Characters using List Sort Function
Let us take an example to illustrate how to sort a list of characters using the list sort function in C++.
Example
#include <iostream>
#include<list>
using namespace std; //using standard namespace
int main() //main function
{
list<char> li={'T','p','o','i','n','t','T','e','c','h'};
list<char>:: iterator itr;
for(itr=li.begin();itr!=li.end();++itr)
std::cout << *itr;
li.sort();
cout<<'\n';
for(itr=li.begin();itr!=li.end();++itr)
std::cout << *itr;
return 0;
}
Output:
Cpp Tutorial
TTcehinopt
Explanation:
In this example, we have created a list of characters named li that is initialized with the character elements {'T','p','o','i','n','t','T','e','c','h'}. After that, we have taken a sort function that sorts the character values on the basis of their ascii values. Finally, it prints the sorted list of a given list, and its output is TTcehinopt.
C++ Example to Sort Custom Objects Using a Comparator
Let us take an example to demonstrate how to sort custom objects using a comparator in C++.
Example
#include <iostream>
#include <list>
#include <string>
using namespace std; //using standard namespace
class Employee {
public:
string name;
int ID;
Employee(string n, inti) : name(n), ID(i) {}
};
// Custom comparison function for sorting by ID
bool compareByID(const Employee &a, const Employee &b) {
return a.ID > b.ID; // Descending order
}
intmain() { //main function
list<Employee>emp = {
{"Johnson", 105},
{"Peter", 102},
{"Michael", 104},
{"Robert", 101}
};
emp.sort(compareByID);
cout<< "Employees sorted by ID (descending):\n";
for (auto &e :emp)
cout<< e.name << " - " << e.ID <<endl;
return 0;
}
Output:
Employees sorted by ID (descending):
Johnson - 105
Michael - 104
Peter - 102
Robert - 101
Explanation:
In this example, we demonstrate how to sort a list of user-defined objects using a custom comparison function. First, we define an Emploayee class with a name and ID that stores multiple objects in a list container . After that, we use the compareByID function to sort employees in descending order of their IDs. At last, it displays the sorted list of employees in descending order.
Features of the List sort function in C++
Several features of the list sort function in C++ are as follows:
- It is a built-in member function of the list container, which is commonly utilized to sort the elements of a list.
- It performs stable sorting, which means the relative order of equivalent elements is preserved.
- The elements can easily be rearranged using the list sort function inside the same list container without destroying the objects.
- The merge sort algorithm is utilized in the C++ list sort function, which is very effective for the linked list. It does not need any random access to sort or arrange the elements.
- It takes only the time complexity, i.e., (O(N log N)).
Conclusion
In conclusion, the list::sort function is a simple and efficient way to sort the elements inside a list container in C++. This function utilizes a merge sort algorithm, which ensures stability and in-place sorting without requiring random access to elements. It is a better option for linked lists, where frequent operations are required, including insertions, deletions, sorting, and many others. With support for custom comparison functions, the list::sort function offers flexibility to arrange elements in any desired order while maintaining optimal performance and simplicity.
C++ List Sort Function FAQ's
1) What is the main purpose of the list::sort function in C++?
In C++, the list sort is a built-in member function of the list container. It is commonly utilized to arrange or sort the elements of a given list in increasing order (ascending order). It does not involve any construction or destruction of elements.
2) Can we utilize the std::sort function with the std::list in C++?
No, because the std::sort function needs random access iterators. In contrast, the list container provides its own sort member function, which can work effectively in bidirectional iterators.
3) Does the list::sort function modify the original list in C++?
Yes. The list::sort function can modify the elements in the original list. It means that the list sort function can arrange the existing elements of the list instead of creating a new list.
4) What is the key distinction between the list::sort function and the forward_list::sort function in C++?
In C++, the main difference between the list::sort and the forwardlist::sort functions is that the list::sort function can be used with bidirectional iterators. In contrast, the forwardlist::sort function can be used with forward iterators.
5) What is the time complexity of the list::sort function in C++?
In C++, the time complexity of the list::sort function is O(N log N).