You may use any sorting algorithm you wish. This may require looking up your 114 textbook or the current 214 textbook. The choices you have are: insertion sort, selection sort, bubble sort, and quicksort.

You will need to modify the algorithm in the following way. Normally, sorting algorithms assume you have an array. However, you can actually sort with pointers too, if you are careful.

If you have an algorithm for, say, bubble sort, rewrite the sorting function as follows:

   void bubblesort( int *begin, int *end )
   {
       // code
   }

where begin points to the first element in the array to be sorted, and end points to one past the last element to be sorted. Once you have this version working, you should be able to easily convert it to a version using iterators since iterators are essentially pointers.

To test your C code, write a test main(), such as:

   int main()
   {
       // jumbled array containing values from 0 to 9, inclusive.
       int arr[ 10 ] = { 9, 3, 2, 8, 7, 1, 6, 0, 4, 5 } ;

       // pass in pointers to element 0 and 10 (which is out of bounds)
       bubblesort( arr, & arr[ 10 ] ) ;

       // Print out to make sure it works. Should see 0 1 2 ... 9
       for ( int i = 0 ; i < 10 ; i++ )
          cout << arr[ i ] << " " ;
        cout << end ;
   }

In your sorting routine, you should not modify the element pointed to by end since this is out-of-bounds and may core dump. However, it is allowed for a pointer to point to an element out of bounds, so long as you don't modify the element the pointer is pointing to.

There is some sorting help in the Tutorial link from the main webpage.

Once this function works, templatize it to create a template function called sort214. See Algorithm.h for the prototype.

sort214 is a template function which works on templatized ArrayList::Iterator objects.

See the class syllabus for policies concerning email Last Modified: Sat Sep 28 23:08:44 EDT 2002

Web Accessibility