Section 22.8 Sorting Parallel Arrays
Often it is useful to store related information about a person or an object in several parallel arrays. For example, we might want to store for each student their name, id, age and gpa. We could then have four arrays for these pieces of information, and for a given index,
i, name[i], id[i], age[i], gpa[i] all make up one student’s record.If we now wanted to sort these student records by id then we’d have to perform all of the array element swaps simultaneously on all four arrays in order to keep records together. This would not be practical or efficient. Take a look at the below example:
Suppose we are using bubble sort in order to sort these student records by id. While Petra’s record is in the correct location, we’ll have to swap Alex’ and Simon’s records during the bubble sort process. In order to keep each student record intact we’d thus not only have to swap
id[2] and id[1] but also simultaneously swap name[2] with name[1], age[2] with age[1] and gpa[2] with gpa[1]. That’s a lot of swaps! This will slow down the sorting process quite a bit. It’s also super confusing. And imagine you wanted to add in additional information to a student record, such as the student’s phone number...Instead, it is more efficient to sort an array of indices - a so-called sort array - and use this array to address data as well as perform all of the swaps on this sort array only. Take a look:
When sorting by id, in the bubble sort algorithm, we now compare
id[sort[i]] with id[sort[i+1]] instead of id[i] with id[i+1]. If necessary, rather than swapping the data, we swap sort[i] and sort[i+1]. In the above illustration for example, we simply swapped sort[1] with sort[2]. Now id[sort[1]] = id[2] is Alex’ id, and id[sort[2]] = id[1] is Simon’s id so that id[sort[0]], id[sort[1]] and id[sort[2]] are in the correct order with respect to each other without ever changing anything within the arrays that hold the data. The only array that is altered during the sorting process is the array sort.
