|
|
|
|
|
|
|
sorted, however, swapping two of them can be time-consuming. The C++ code to swap two structs is the same, regardless of the size of the structsan ordinary assignment statement will do. But the length of time to make the swap varies greatly depending on the size of the structs. For example, it may take 10 times as long to swap structs with 20 members as it does to swap structs with 2 members. |
|
|
|
|
|
|
|
|
If we are dealing with large structs, we can make the sorting operation more efficient and save memory by making the structs dynamic variables, and by sorting pointers to the structs rather than sorting the structs themselves. This way, only simple pointer variables are swapped on each iteration, rather than whole structs. |
|
|
|
|
|
|
|
|
The SelSort function has to be modified somewhat to sort large structs rather than simple variables. The structs themselves are dynamically allocated, and a pointer to each is stored in an array. It is these pointers that are swapped when the algorithm calls for exchanging two values. |
|
|
|
|
|
|
|
|
We have to declare an array ptrList, which holds pointers to the personnel records, to be the maximum size we might need. However, we create each PersonnelData variable only when we need it. Therefore, room for 1000 pointers is set aside in memory for the ptrList array, but at run time there are only as many PersonnelData variables in memory as there are records in the file (see Figure 17-14). |
|
|
|
|
|
|
|
|
The ptrList array before and after sorting is shown in Figure 17-15. Note that when the algorithm wants to swap the contents of two structs, we swap the pointers instead. |
|
|
|
|
|
|
|
|
Now that we have chosen a concrete data representation for the personnel record list, we should review the ADT operations once more. We identified |
|
|
|
|
|
|
|
|
Figure 17-14
Array of Pointers to PersonnelData Structs |
|
|
|
|
|
