This year, thousands of students took the SAT (Scholastic Aptitude Test) in New

Question

This year, thousands of students took the SAT (Scholastic Aptitude Test) in New Jersey in preparation enter college. The total score on the SAT is out of 2400-scores are in multiples of 10. You are asked by the SAT office to write a program that will sort the students in descending values of their scores. If two students have the same score, it does not matter in which order they appear in the sorted result. Assume that the computer on which you will run your program has enough memory to store the names and scores of all the students, either in an array or in a linked list. Also, for this question, you can assume the number of students who took the SAT this year is exactly 65,536, which is 2^16

Assuming you were to use mergesort with linked lists, and counting only each score-to-score comparison as a unit time operation, how many such unit time operatons (not big O) would it take in the worst case to do the sort? Your answer must be simplified to the least possible number of terms.

Come up with an algorithm that is better than mergesort above, i.e. it makes fewer unit time operations in the worst case. State what data structure(s) you will use, and clearly describe your algorithm. Then specify what unit time operations you are counting, and determine the total number of such units. You will NOT get any credit if your algorithm is not better than mergesort for this application, even if it works, and you have analyzed it correctly.

Explanation / Answer

First, our base case: If the array contains 0 or 1 elements, there is nothing to do. It is already sorted.

If the array has two or more elements in it, we will break it in half, sort the two halves, and then go through and merge the elements.
The Java method to do it:

public void sort(int[] array) {
// create tempArray for use in merging
int[] tempArray = new int[array.length];
mergeSort(array, 0, array.length-1, tempArray);
}

/*
* PRE: left and right are valid indexes of array.
* tempArray.length == array.length
* POST: Sorts array from left to right.
*/
public void mergeSort(int[] array, int left, int right, int[] tempArray) {
if (left < right) {
int middle = (right + left) / 2;
mergeSort(array, left, middle, tempArray);
mergeSort(array, middle + 1, right, tempArray);
merge(array, left, middle, right, tempArray);
}
}
The method merge takes the sorted elements in array[left..middle] and array[middle+1..right] and merges then together using the array tempArray, and then copies them back into array.

  
/** PRE: left <= middle <= right and left,middle,right are valid
* indices for array * tempArray.length == array.length
* array[left..middle] and array[middle+1..right] must both be sorted.
* POST: Merges the two halves (array[left..middle] and
* array[middle+1..right]) together, and array[left..right] is then
* sorted.
*/
private void merge(int []array, int left, int middle,
int right, int[] tempArray) {
int indexLeft = left;
int indexRight = middle + 1;
int target = left;

// Copy both pieces into tempArray.
for (int i = left; i <= right; i++) {
tempArray[i] = array[i];
}
  
// Merge them together back in array while there are
// elements left in both halves.
while (indexLeft <= middle && indexRight <= right) {
if (tempArray[indexLeft] < tempArray[indexRight]) {
array[target] = tempArray[indexLeft];
indexLeft++;
} else {
array[target] = tempArray[indexRight];
indexRight++;
}
target++;
}

// Move any remaining elements from the left half.
while (indexLeft <= middle) {
array[target] = tempArray[indexLeft];
indexLeft++;
target++;
}

// Move any remaining elements from the right half.
while (indexRight <= right) {
array[target] = tempArray[indexRight];
indexRight++;
target++;
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.