Java code:: Undergraduate students are surprised to learn that as much intellect

Question

Java code:: 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.

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.

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 ratio of comparisonCnt values for 2000 elements and 1000 elements.

Document the ratio of comparisonCnt values for 1000 elements and 2000 elements

Explanation / Answer

The Followin java code will do whatever the question has asked, I have commented in the code for your better understanding and if you have any doubt you can ask me in the comment section.

The selection sort algorithm will be checking for the for the smallest in the list and storing it at its place and then again 2nd smallest and then it goes on for next smallest items placing in their respective places.its average time complexity is theta(n^2)

import java.util.*;
/**
*
* @author Asif
*/
public class SelectionSort {
//Method for selection sort
public static double[] selectionSort(double[] a)
{
int i=0,index=0,dataSwaps=0,noOfCamparisons=0;
double number;
while(i<a.length){
index=i;
for (int j=i+1;j<a.length;j++){
noOfCamparisons++;
if(a[j]<a[i]){
index=j;
}
}
dataSwaps++;
number=a[index];
a[index]=a[i];
a[i]=number;
i++;
}
System.out.println("no of Swaps = "+dataSwaps);
System.out.println("no of comparisons = "+noOfCamparisons);
  
return a;
}
//Main method
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
System.out.println("Enter value for NUM_ELEMENTS :");
final int NUM_ELEMENTS=sc.nextInt(); //NUM_ELEMENTS has been declared final
double[] lo2hi=new double[NUM_ELEMENTS];
double[] hi2lo=new double[NUM_ELEMENTS];
double[] random=new double[NUM_ELEMENTS];
System.out.println("ENTER VALUE FOR lo2hi : ");
for(int i=0;i<NUM_ELEMENTS;i++){
lo2hi[i]=i+1;
}
int k=0;
System.out.println("ENTER VALUE FOR hi2lo : ");
for(int j=NUM_ELEMENTS-1;j>=0;j--){
hi2lo[k++]=j;
}
System.out.println("ENTER VALUE FOR random : ");
for(int i=0;i<NUM_ELEMENTS;i++){
random[i]=Math.random();
}
lo2hi=selectionSort(lo2hi);
hi2lo=selectionSort(hi2lo);
random=selectionSort(random);
System.out.println("sorted VALUES FOR lo2hi : ");
for(int i=0;i<NUM_ELEMENTS;i++){
System.out.println(lo2hi[i]);
}

System.out.println("sorted VALUEs FOR hi2lo : ");
for(int i=0;i<NUM_ELEMENTS;i++){
System.out.println(hi2lo[i]);
}

System.out.println("sorted VALUEs FOR random : ");
for(int i=0;i<NUM_ELEMENTS;i++){
System.out.println(random[i]);
}
}
}
//no of comparisons for 1000=499500
//no of comparisons for 2000=1999000
//comparison ratio for 1000 to 2000= 0.24987493746873438
//comparison ratio 2000 to 1000=4.002002002002002

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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