PLEASE HELP IN JAVA: Write a recursive version of Selection Sort, and compare th

Question

PLEASE HELP IN JAVA:

Write a recursive version of Selection Sort, and compare the time it takes with the non-recursive version. Use words.txt as your input file and input the data into two arrays so you can use one array with each sort.

THINK ABOUT WHY I ASKED YOU TO USE TWO ARRAYS. THIS IS A HINT TO HELP YOU CREATE A WELL DESIGNED AND EFFICIENT ALGORITHM

IF you used one array and sorted it you could store the time somewhere. You could then go back to the top of your input file and get all the data from the input file a second time and do a second sort. You have only used one array, but you have collected the data from the data file TWICE. I/O takes a lot more time than processing time, so you have just eaten up a lot of time and overhead collecting your data twice.

If you collect your data ONCE and then load two arrays with the same string each time you will have two identical arrays. Yes, you will be using twice the storage, but your transmission time (in getting the input) will be halved.

Insert a timer so we can see how long each sort takes. When you submit the assignment, in the comments state how long your non-recursive method took, how long the recursive one took, and whether one was clearly better than the other.

This assignment really only requires you to alter a few lines of code in the non-recursive selection sort. However, it tests your ability to think recursively, which is what will be required in the following chapters. So start thinking about it early, don't give up, and get your 'recursive' hat on!!

You will need to know how to use a timer.

WORDS.TXT:

noncollectable

reallocation

drenching

obnoxious

venality

dybbuk

shotgun

changelessly

handiwork

unheralded

dovecote

anode

spellbind

psychologist

improvisational

.......

Explanation / Answer

I hope you will like the solution. kept it very simple

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
*
* @author Sam
*/
public class SelectionSort {

  
    static void sortRecursicve(String[] arr, int n) {
        if (n == 1)
            return;
      
        int max = 0;
        for (int i = 1; i < n; i++)
           if (arr[i].compareTo(arr[max]) > 0)
               max = i;
        String tmp = arr[max];
        arr[max] = arr[n - 1];
        arr[n - 1] = tmp;
        sortRecursicve(arr, n - 1);
    }
  
  
    static void sort(String[] arr, int n) {
        for (int i = n-1; i > 0; i--) {
            int max = 0;
            for (int j = 1; j < i; j ++)
                if (arr[j].compareTo(arr[max]) > 0)
                    max = i;
            String tmp = arr[max];
            arr[max] = arr[i - 1];
            arr[n - 1] = tmp;
        }
    }
  
    public static void main(String[] args) throws IOException {
        String fileName;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Input file name: ");
        fileName = br.readLine();
        File file = new File(fileName);
        String[] words1 = new String[1000];
        String[] words2 = new String[1000];
        int count = 0;
        br = new BufferedReader(new FileReader(fileName));
      
        while ((words1[count] = br.readLine())!=null) {
            words2[count] = words1[count];
            count++;
        }
      
        long start = System.nanoTime();
        sortRecursicve(words1, count);
        long time = System.nanoTime() - start;
      
        System.out.println("Recursive Sorting took " + time + " nano seconds");
        System.out.print("Result: | ");
        for (int i = 0; i < count; i++)
            System.out.print(words1[i] + " | ");
      
      
        start = System.nanoTime();
        sort(words2, count);
        time = System.nanoTime() - start;
      
        System.out.println("Sorting took " + time + " nano seconds");
        System.out.print("Result: | ");
        for (int i = 0; i < count; i++)
            System.out.print(words2[i] + " | ");
    }
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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