|
|
The List sort()
function provides an efficient
method for sorting a List in place, for example, L.sort(LessThan)
.
sort()
uses a mergesort algorithm, which is O(nlog n) in complexity.
(See the examples in the section,
``Example'',
for an insertion sort()
operation with quadratic
complexity.)
Because no total ordering or T::operator<()
is assumed on T, the user must provide a function to do the comparison between
elements of the List.
This user-defined function has type int (*)(const
T&,const T&)
for sorting a List<T>
and int (*)(const T*&,const T*&)
for sorting a
List_of_p<T>
.
All this really means is that
the function, for example, LessThan()
, has the following
signature:
int LessThan( const T&, const T& ); // for Listsor
int LessThan( const T*&, const T*& ); // for List_of_psThis function is expected to return a nonzero integer if its first argument is less than its second, and 0 otherwise. As an example, consider the following class and comparison functions:
class Student {
String name;
String grade;
public:
Student(const String&,const String&);
Student(const Student&);
int operator==(const Student&);
friend ostream& operator<<(ostream&,
const Student&);
friend int name_compare(const Student&,
const Student&);
friend int grade_compare(const Student&,
const Student&);
};
int name_compare(const Student& s1,
const Student& s2)
{
if(s1.name + s1.grade < s2.name + s2.grade)
return 1;
return 0;
}
int grade_compare(const Student& s1,
const Student& s2)
{
if(s1.grade < s2.grade)
return 1;
return 0;
}
These comparison functions can now be used to sort a List of Foos two different ways in the following program:
#include <Student.h>
#include <List.h>
#include <iostream.h>
main()
{
Student s1("George","A");
Student s2("Arthur","D");
Student s3("Chester","C");
Student s4("Willy","B");
List<Student> Class(s1,s2,s3,s4);
cout << Class << "\0;
Class.sort(name_compare);
cout << Class << "\0;
Class.sort(grade_compare);
cout << Class << "\0;
}
would have the following output:
( George: A, Arthur: D, Chester: C, Willy: B )
( Arthur: D, Chester: C, George: A, Willy: B )
( George: A, Willy: B, Chester: C, Arthur: D )
The sort()
operation does not preserve the
position of any of the iterators (see the section,
``List iterators''.
It is the responsibility of the user to reset the iterators
after the sort()
operation.