Pointer Sort



Pointer Sort Construction Algorithm

A pointer sort uses an auxiliary array that contains pointers to an array of items to be sorted. Usually, the items to be sorted are records and that assumption is made in the following discussion. The pointers can either contain indexes into the record array or actual addresses of the records. In this discussion, indexes will be used, but your booklet contains InsRecAP.cpp and InsRecIP.cpp. These are complete programs that demonstrate Address Pointers (AP) and Index Pointers (IP).

In a pointer sort, there are two arrays.

P the pointer array will usually be initialized with 0(ArraySize-1. (In this example, it is 0(ArraySize because of the sentinel value at location 0)

A the array containing the records.

In a normal sort, we would sort A by rearranging the records. In a pointer sort, A will never be changed, instead the pointer array P will be altered. When the sort is complete, P[0] will contain the index of the record with the smallest key. P[1] will contain the index of the record having the second smallest key, and so on.

After both arrays are assigned their initial values, a standard comparison sort can be converted into a pointer sort by making the following changes to the algorithm.

1. Change each comparison so that it is made indirectly through the pointer array. Each A[i].key in a comparison becomes A[P[i]].key.

2. Change each swap so that the corresponding pointers are swapped, not the records. For example: A[i] = A[i-1] becomes P[i] = P[i-1].

A pointer sort can allow you to have the same data sorted simultaneously on several keys. Simply create one pointer array for each desired key. A pointer version of a sort may be faster or slower than the standard version. The conversion makes each comparison slower because of the double indexing, but each swap is likely to be faster as you are swapping integers rather than records.

On the next page, you can see both standard and pointer versions of the insertion sort in a pseudo C++. Interestingly, if the items being sorted are Java or C++ objects, then you will probably be performing a pointer sort automatically, whether you try to or not. When you attempt to swap two objects in Java, you will likely be swapping their addresses. I will have to check this out, but it looks right.

Standard Insertion Sort: Assume A[0].key = a value lower than any in the array.

Read in records storing them in A[1] through A[n].

int i,j; /* indices */ Record tempRec; /* Temporary record for swapping */

for( i = 2; i ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download