In C++, the list container plays a crucial role in the Standard Template Library (STL). This container is structured as a doubly linked list, offering great flexibility for inserting and removing elements from various positions, be it either end or a specific location.
In C++, the sort function within the list container is an inherent member function. This function is frequently employed to organize or reorder the items within a specified list in ascending order. No creation or deletion of elements is carried out during this process. Instead, elements are simply rearranged within the container. This function is classified as a member function due to the limitation of linked lists in providing random access iterators in C++.
Syntax
It has the following syntax in C++.
void sort();
In this particular syntax,
- Argument: It lacks any parameter.
- Output: It does not yield any value.
C++ Simple List Sort function Example
Let's consider an example to showcase the functionality of the sort method 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 instance, a list of integers called li has been established, containing the values {6, 4, 10, 2, 4, 1}. Following this, the sort method is applied to arrange the elements in increasing order. Finally, the sorted version of the specified list is showcased, resulting in the sequence 1 2 4 4 6 10.
C++ Example to Sort a List of Characters using List Sort Function
Let's consider a scenario to demonstrate the process of arranging a character list by employing the list sort method 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 instance, a character list named li has been generated with initial values {'T','p','o','i','n','t','T','e','c','h'}. Subsequently, a sorting function has been applied to arrange the characters based on their ASCII values. Ultimately, the program displays the sorted list derived from the initial list, resulting in the output TTcehinopt.
C++ Example to Sort Custom Objects Using a Comparator
Let's consider an illustration to showcase the process of sorting custom objects with 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 instance, we illustrate the process of sorting a collection of user-defined objects by implementing a custom comparator function. Initially, we establish a class named Employee containing attributes such as name and ID to store numerous instances within a list data structure. Subsequently, we employ the compareByID method to arrange the employees in a descending sequence based on their IDs. Finally, the organized list of employees in descending order is presented.
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 summary, the list::sort method provides a straightforward and effective approach to arranging elements within a list container in C++. This method employs a merge sort algorithm, guaranteeing stability and in-place sorting without the need for random element access. It proves to be advantageous for linked lists that necessitate frequent operations like insertions, deletions, sorting, and more. By accommodating custom comparison functions, the list::sort function allows for arranging elements in various orders while upholding efficiency and ease of use.
C++ List Sort Function FAQ's
The primary objective of the list::sort function in C++ is to arrange the elements within a list in a specified order based on a comparison function.
In C++, the sort function is an inherent member function of the list container. It is frequently employed to organize or rearrange the elements of a specified list in ascending order. This process does not entail creating or deleting any elements.
Yes, it is possible to use the std::sort function with the std::list container in C++.
No, as the std::sort function specifically requires random access iterators. On the other hand, the list container offers its own sort member function tailored for bidirectional iterators, ensuring efficient functionality in this context.
No, the list::sort function in C++ does not modify the original list; it only reorders the elements within the list.
Yes, the list::sort method has the capability to alter the elements within the original list. In essence, this signifies that the list sort method is capable of reorganizing the current elements of the list rather than generating a fresh list.
The main difference between the list::sort function and the forwardlist::sort function in C++ lies in the type of container they operate on. The list::sort function is designed for doubly linked lists while the forwardlist::sort function is tailored for singly linked lists.
In C++, a key contrast between the sort function for list and forwardlist is that list::sort supports bidirectional iterators, while forwardlist::sort is compatible with forward iterators.
5) What is the computational complexity of the list::sort method in the C++ programming language?
In C++, the time complexity of the list::sort method is O(N log N).
