

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 userdefined 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.