Question

JAVA Programming.

How Long is this Gonna Take?

Undergraduate students are surprised to learn that as much intellectual energy has been invested in sorting and searching as almost any other part of Computer Science. Think of Duke Energy's customer database—it’s huge. New customers have to be added, former ones deleted, bills must be sent out, customers send in their payments and inquire about their accounts. An efficient data organization is required for Duke to function at all. The first attack on organizing data involves sorting data elements into some order, and exploiting that order when trying to retrieve a particular element.

Hundreds of sorting algorithms have been developed, and like all sorting algorithms, Selection Sort accomplishes its task by making comparisons and data movements. We often compare algorithms by counting the number of comparisons and movements required—the fewer the better. This begs the question, how many comparisons and movements does the Selection Sort make? And, are these actions affected by the initial arrangement of data values in the array? This is the focus of this lab.

Objectives

By the end of this lab students should be able to

• Allocate arrays
• Initialize an array with random numbers
• Initialize an array to be contain monotonically increasing and decreasing values
• Sort arrays
• Explain how sorting time increases as the number of elements to be sorted increases

Collecting Sorting Data

Start with the SelectionSort class in the zip file attached to this item. Keep the name SelectionSort, and add a main method to it.

• Modify the selectionSort method to have two counters, one for the number of comparisons, and one for the number of data swaps. Each time two data elements are compared (regardless of whether the items are in the correct order—we're interested in that a comparison is being done at all), increment the comparison counter. Each time two data items are actually swapped, increment the data swap counter.
• At the end of the selectionSort method, print the size of the sorted array, and the counters. (Be sure to identify which counter is which in your print message
• In your main method,
  • Declare a final int, NUM_ELEMENTS. Initially set NUM_ELEMENTS to 10 to debug your program.
  • Declare and create three double arrays of NUM_ELEMENTS length, lo2Hi, hi2Lo, random.
  • Initialize the first array, lo2Hi, with values 1.0, 2.0, …, NUM_ELEMENTS
  • Initialize the second array, hi2Lo with values NUM_ELEMENTS, 24.0,…, 1.0
  • Initialize the third array, random, with random double values between 0.0 and less than 1.0
  • call the selectionSort method using each array. (Note: you might want to print the array elements themselves for debugging purposes when NUM_ELEMENTS is small, but you’ll not want to print them with larger values for NUM_ELEMENTS.)
• Run your program three times with different values for NUM_ELEMENTS: 1000, 2000 and 4000.

In your submission write some text describing the relationship between the number of comparisons of the various values of NUM_ELEMENTS. For example, what do we find if we divide the number of comparisons for 2000 elements by the number of comparisons for 1000 elements? What do we find if we divide the number of comparisons for 4000 elements by the number of comparisons for 2000 elements?

Epilog: As you can tell, Selection sort doesn’t scale very well. The number comparisons increase quadradically as a function of number of elements. There comes a point that, because of array size, it’s impractical to use Selection sort. The good news is there are hundreds of sorting algorithms. Some suffer from the same performance shortcomings as Selection sort, but others that are almost “magical” in that increasing the number of elements has minor impact on performance. If you’re interested, take a look at chapter 23 Sorting.

Reporting Sorting Data

Submit, in addition to your program, submit the following information in some understandable form (it doesn’t have to be this exact table, but your submission should contain this information).

	1000 elements	2000 elements	4000 elements
Comparison count lo2Hi
Comparison count hi2Lo
Comparison count random
Swap count lo2Hi
Swap count hi2Lo
Swap count random

Increasing the number of elements from 1000 to 2000 increases the number of comparisons by a factor of	Increase factor
Increasing the number of elements from 2000 to 4000 increases the number of comparisons by a factor of	Increase factor

Grading Elements

• use class SelectionSort with the selectionSort method
• instrument selectionSort with comparisonCnt and swapCnt, and print the number of array elements and the comparisonCnt and swapCnt values
• write a main method with final int NUM_ELEMENTS
• declare and create three double arrays of length NUM_ELEMENTS
• initialize the arrays as specified
• call selectionSort with each array
• Run the SelectionSort with different values for NUM_ELEMENTS: 1000, 2000 and 4000.
• Document the 18 data values described above.
• Document the ratio of comparisonCnt values for 2000 elements and 1000 elements.
• Document the ratio of comparisonCnt values for 4000 elements and 2000 elements

SelectionSort.java 
public class SelectionSort {
  /** The method for sorting the numbers */
  public static void selectionSort(double[] list) {
    for (int i = 0; i < list.length - 1; i++) {
      // Find the minimum in the list[i..list.length-1]
      double currentMin = list[i];
      int currentMinIndex = i;

      for (int j = i + 1; j < list.length; j++) {
        if (currentMin > list[j]) {
          currentMin = list[j];
          currentMinIndex = j;
        }
      }

      // Swap list[i] with list[currentMinIndex] if necessary;
      if (currentMinIndex != i) {
        list[currentMinIndex] = list[i];
        list[i] = currentMin;
      }
    }
  }
}

Answer 1

1.