A List Class Library for C++ - List(C++)

Sort operation

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 Lists
   int LessThan( const T*&, const T*& );  // for List_of_ps
This 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;
      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.grade < + 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.

Next topic: Queue-oriented operations
Previous topic: Comparisons

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005