Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 15

name id

0
1
2

Graham, Ariel
Perrott, Chloe

3050
2795

Charles, Kandice 4455

3 Seecharan, Anella 7824

4 Reyes, Aaliyah 6669

5 Graham, Ashleigh 5000

6 Reyes, Ayanna 5464

7 Greaves, Sherrelle 6050

Figure 1-1. Two arrays with related information

Consider the problem of sorting the names in alphabetical order. At the end, we would want each name to have
its correct ID number. So, for example, after the sorting is done, name[0] should contain “Charles, Kandice” and id[0]
should contain 4455 .
To achieve this, each time a name is moved during the sorting process, the corresponding ID number must also
be moved. Since the name and ID number must be moved “in parallel,” we say we are doing a “parallel sort” or we are
sorting “parallel arrays.”
We rewrite insertionSort3 to illustrate how to sort parallel arrays. We simply add the code to move an ID
whenever a name is moved. We call it parallelSort .

public static void parallelSort(String[] list, int id[], int lo, int hi) {
//Sort the names in list[lo] to list[hi] in alphabetical order,
//ensuring that each name remains with its original id number.
for (int h = lo + 1; h <= hi; h++) {
String key = list[h];
int m = id[h]; // extract the id number
int k = h - 1; //start comparing with previous item
while (k >= lo && key.compareToIgnoreCase(list[k]) < 0) {
list[k + 1] = list[k];
id[k+ 1] = id[k]; //move up id number when we move a name
--k;
}
list[k + 1] = key;
id[k + 1] = m; //store the id number in the same position as the name
} //end for
} //end parallelSort

We test parallelSort by writing Program P1.4.

Program P1.4

import java.util.*;
public class ParallelSort {
final static int MaxNames = 8;
public static void main(String[] args) {
String name[] = {"Graham, Ariel", "Perrott, Chloe",
"Charles, Kandice", "Seecharan, Anella", "Reyes, Aaliyah",
"Graham, Ashleigh", "Reyes, Ayanna", "Greaves, Sherrelle" };
int id[] = {3050,2795,4455,7824,6669,5000,5464,6050};

parallelSort(name, id, 0, MaxNames - 1);