8.3.1 Maximum Entry Sort

Perhaps the most straightforward way to sort numbers in an array into decreasing* order is to begin by placing the largest number in element 1. The next largest number is then placed into element 2, and so on. The maximum entry sort repeatedly finds the next largest array entry and places it in its proper position in the array. Suppose the point has been reached in this procedure where the k largest numbers have been properly placed into the first k elements of the array data. Assume a variable next points to the element of data into which the next largest element is to be placed. Next must now be updated to next + 1 so that it contains the value k + 1, as indicated in Figure 8.3.

* The sorting programs assume that decreasing order is desired. They can easily be modified to sort in increasing order.

Assume that a function maxloc exists, with parameters data, next, and n, the array length. Maxloc returns with its value indexing the largest element between the nextth and the nth elements of data. The sort may then be obtained by a loop in which maxloc is invoked (n - 1 times, with next taking on values 1, 2, . . . , n - 1, respectively, on each call. Within the loop, when each call to maxloc is made, an exchange between data [next] and data[maxloc] occurs.

Maxloc might be implemented by traversing the elements next to n of data. Each time a new element is accessed, it is compared to a variable, largest, containing the largest entry seen so far in this traversal. If the new element is greater than largest, largest is set to the new element value, and maxloc is set to point to the location of the new element in data.

This algorithm is probably similar to what most peole do instinctively when confronted with a small sorting problem. It may be implemented as in the procedure maxentrysort.

Figure 8.3 Ready to Determine the Next Largest

#define MAX 100

typedef struct

{

int key;

}record;

typedef record recordarray[MAX];

maxloc (data,next,n)

/* Returns the array index of the

largest entry in data between the

entries indexed by next and n.

*/

recordarray data;

int next,n;

{

int largest,i,tmaxloc;

tmaxloc = next;

largest = data[next].key;

for (i = next + 1; i <= n; i++)

>Comment

if (data[i].key > largest)

{

tmaxloc = i;

largest = data[i].key;

return (tmaxloc);

}

}

maxentrysort (data, n)

/* Sorts the n records stored in array data

in descending order.

*/

recordarray data;

int n;

{

int next, loc;

for (next=1; next<=n - 1; next++)

{

loc = maxloc (data,next,n);

>Comment

interchange (data, next, loc);

}

}

For the simple record used here for illustration, the interchange function is as follows.

interchange (data, i, j)

/* Interchanges the entries of

array data indexed by i and j.

*/

recordarray data;

int i,j;

{

record tempdata;

tempdata.key = data[i].key;

data[i].key = data[j].key;

data[j].key = tempdata.key;

}

How much time does this implementation of the maximum entry sort take? One interchange is made on each call to maxloc for a total of n - 1 interchanges. The number of comparisons is (n - k) on the call to maxloc, when next has the value k. The total number of comparisons is (n - 1) + (n - 2) + . . . + 2 + 1, which sums to [n(n - 1)]/2. Thus the time is determined by the time of the (n - 1) interchanges plus the time of the [n(n - 1)]/2 comparisons. Each interchange takes a constant amount of time, and each comparison takes, at most, a constant amount of time. The result is O(n2) time. This means that if n is doubled or tripled, the time will increase by a factor of about 22, or 4, and 32, or 9, respectively, when n is large. For n = 105, the time is roughly proportional to 1/2 1010, which is within a factor of 100 of 1013, the guide for feasibility presented in Chapter 1. Quicker algorithms are obviously needed for large n, and even perhaps for small n. The next elementary sort technique offers some improvement.