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.
Pthe pointer array will usually be initialized with 0ArraySize-1. (In this example, it is 0ArraySize because of the sentinel value at location 0)
Athe 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<= n; i++ )
{j = i;
while( A[j].key < A[j-1].key )// compare keys
{tempRec = A[j];// swap records
A[j] = A[j-1];
A[j-1] = tempRec;
j --;
}
}
Pointer Version of Insertion Sort Using Indexes ( or you could use pointers)
( A[0].key = a value lower than any in the array )
Initialize P to be 0 .. n// Not n-1 because of the sentinel value
Read in records A[1] through A[n]// Initialize the data
int i, j, temp;// temp is an int as only indexes are swapped
for( i = 2; i<=n; i++ )
{j = i;
while( A[P[j]].key < A[P[j-1]].key )// compare keys indirectly thru P
{temp = P[j];// swap index pointers
P[j] = P[j-1];
P[j-1] = temp;
j --;
}
}
After the index pointers are rearranged, the data can be output in sorted order by executing something like:
for( i = 1; i<= n; i++ ) Output the record at A[P[i]];
A similar piece of code could copy from array A to a second array (Sorted), which would then contain the array in sorted order.
for( i = 1; i <= n; i++ ) Sorted[i] = A[P[i]];