Create a program named sort.java that reads in primes1.txt (unsorted prime numbe

Question

Create a program named sort.java that reads in primes1.txt (unsorted prime numbers less than one million) and stores them into an ArrayList. Compare sorting this list using the bubble sort, selection sort, and merge sort. Each sort should list the elapsed time, iterations, and print the first 10 and last 10 numbers in the array.

Extra Credit: add another sorting algorithm of your choice.


Example output
This program compares the bubble, selection, merge sorts.
The data set is 78498 unsorted integers (prime numbers less than 1,000,000)

1. Bubble Sort
Time to sort = ??? seconds
Number of iterations = ???
First 10 - 2 3 5 7 11 17 23 29 31 37
Last 10 - 999883 999863 999907 999917 999931 999953 999959 999961 999979 999983

2. Selection Sort
Time to sort = ??? seconds
Number of iterations = ???
Last 10 - 999883 999863 999907 999917 999931 999953 999959 999961 999979 999983

3. Merge Sort
Time to sort = ??? seconds
Number of iterations = ???
Last 10 - 999883 999863 999907 999917 999931 999953 999959 999961 999979 999983

MY program so

import java.io.*;
public class sorts
{
   static ArrayList<Integer> Data1 = new ArrayList<Integer>();
   static ArrayList<Integer> Data2 = new ArrayList<Integer>();
   static ArrayList<Integer> Data3 = new ArrayList<Integer>();
   static int Iterations1=0, Iterations2=0, Iterations3=0;

   public static void main(String[] args) throws IOException
   {
       int A = 0, Temp = 0;
       File file = new File("primes1.txt");
       Scanner infile = new Scanner(file);

       while (infile.hasNextInt())
       {
           A = infile.nextInt();
           Data1.add(A); Data2.add(A); Data3.add(A);
       }
       // Bubble Sort
       long startTime = System.nanoTime();
       for (int x=0; x<Data1.size(); x++)
       {
           //System.out.println(x);
           for (int y=0; y<Data1.size()-1-x; y++)
           {
               if (Data1.get(y) > Data1.get(y+1))
               {
                   Iterations1++;
                   Temp = Data1.get(y);
                   Data1.set(y, Data1.get(y+1));
                   Data1.set(y+1, Temp);
               }
           }
       }
       long endTime = System.nanoTime();
       System.out.println("Bubble Sort Seconds = " + (double)((endTime - startTime)/1000000000.0));
       for (int x=0; x<10; x++)
       {
           System.out.print(Data1.get(x) + " ");
       }
       System.out.println();
      
       long startTime= system.nanoTime();
       for (int x=0; x<Data2.size() - 1; x++)
       {
           int index=x;
           for( int j =i +1;j < Data2.lenght; j++)
           if(y=0; y<Data2.size-1-x;y++)
           {
              Iteration1++;
              Temp=Data2.set(y);
              Data2.set(y,Data2.get(y+1));
              Data2.set(y+1,Temp);
}      
         
       }  
      

       startTime = System.nanoTime();
       Data3 = MergeSort(Data3);
       endTime = System.nanoTime();
       System.out.println("Merge Sort Seconds = " + (double)((endTime - startTime)/1000000000.0));
       for (int x=0; x<10; x++)
       {
           System.out.print(Data3.get(x) + " ");
       }
       System.out.println();
   }

   static ArrayList<Integer> MergeSort(ArrayList<Integer> dataset)
   {
       Iterations3++;
       if (dataset.size() == 1) return dataset;
       else
       {
           // split data into 2 parts
           ArrayList<Integer> LeftData = new ArrayList<Integer>(dataset.subList(0,dataset.size()/2));
           ArrayList<Integer> RightData = new ArrayList<Integer>(dataset.subList(dataset.size()/2,dataset.size()));
           dataset = Merge(MergeSort(LeftData), MergeSort(RightData));
       }
       return dataset;
   }

   // merge the left and right lists together
   static ArrayList<Integer> Merge(ArrayList<Integer> LeftData, ArrayList<Integer> RightData)
   {
   ArrayList<Integer> MergedData = new ArrayList<Integer>();
   while (LeftData.size() > 0 || RightData.size() > 0)
   {
           Iterations3++;
   if (RightData.size() == 0)
   {
   MergedData.add(LeftData.get(0));
   LeftData.remove(0);
   }
   else if (LeftData.size() == 0)
   {
   MergedData.add(RightData.get(0));
   RightData.remove(0);
   }
   else if (LeftData.get(0) < RightData.get(0))
   {
   MergedData.add(LeftData.get(0));
   LeftData.remove(0);
   }
   else
   {
   MergedData.add(RightData.get(0));
   RightData.remove(0);
   }
   }
   return MergedData;
   }
}

Explanation / Answer

Comments added..

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class Test {

static ArrayList<Integer> Data1 = new ArrayList<Integer>();
static ArrayList<Integer> Data2 = new ArrayList<Integer>();
static ArrayList<Integer> Data3 = new ArrayList<Integer>();
static int Iterations1 = 0, Iterations2 = 0, Iterations3 = 0;

public static void main(String[] args) throws IOException {
int A = 0, Temp = 0;
//reading text file
File file = new File("primes1.txt");
Scanner infile = new Scanner(file);
//reading numbers from file and storing back to arraylists
while (infile.hasNextInt()) {
A = infile.nextInt();
Data1.add(A);
Data2.add(A);
Data3.add(A);
}
// Bubble Sort
long startTime = System.nanoTime();
for (int x = 0; x < Data1.size(); x++) {
//System.out.println(x);
//bubble sorting
for (int y = 0; y < Data1.size() - 1 - x; y++) {
if (Data1.get(y) > Data1.get(y + 1)) {
Iterations1++;
Temp = Data1.get(y);
Data1.set(y, Data1.get(y + 1));
Data1.set(y + 1, Temp);
}
}
}
//printing results
long endTime = System.nanoTime();
System.out.println("Bubble Sort Seconds = " + (double) ((endTime - startTime) / 1000000000.0));
System.out.println("Iterations: "+Iterations1);
System.out.println("First Ten numbers: ");
for (int x = 0; x < 10; x++) {
System.out.print(Data1.get(x) + " ");
}
System.out.println("Last Ten numbers: ");
for (int x = Data1.size(); x < Data1.size()-10; x--) {
System.out.print(Data1.get(x) + " ");
}
System.out.println();

  
//selection sortinh
startTime = System.nanoTime();
for (int i = 0; i < Data2.size() - 1; i++) {
int index = i;
for (int j = i + 1; j < Data2.size(); j++) {
if (Data2.get(j) < Data2.get(index)) {
index = j;
}
}
Iterations2++;
int smallerNumber = Data2.get(index);
Data2.set(index, i);
Data2.set(i, smallerNumber);
}
endTime = System.nanoTime();
//printing results
System.out.println("Selection Sort Seconds = " + (double) ((endTime - startTime) / 1000000000.0));
System.out.println("Iterations: "+Iterations2);
System.out.println("First Ten numbers: ");
for (int x = 0; x < 10; x++) {
System.out.print(Data2.get(x) + " ");
}
System.out.println("Last Ten numbers: ");
for (int x = Data2.size(); x < Data2.size()-10; x--) {
System.out.print(Data2.get(x) + " ");
}
System.out.println();
  
//Merge sorting
startTime = System.nanoTime();
//calling method
Data3 = MergeSort(Data3);
endTime = System.nanoTime();
//Printing results
System.out.println("Merge Sort Seconds = " + (double) ((endTime - startTime) / 1000000000.0));
System.out.println("Iterations: "+Iterations3);
System.out.println("First Ten numbers: ");
for (int x = 0; x < 10; x++) {
System.out.print(Data3.get(x) + " ");
}
System.out.println("Last Ten numbers: ");
for (int x = Data3.size(); x < Data3.size()-10; x--) {
System.out.print(Data3.get(x) + " ");
}
System.out.println();
}

//merge sorting methods
static ArrayList<Integer> MergeSort(ArrayList<Integer> dataset) {
Iterations3++;
if (dataset.size() == 1) {
return dataset;
} else {
// split data into 2 parts
ArrayList<Integer> LeftData = new ArrayList<Integer>(dataset.subList(0, dataset.size() / 2));
ArrayList<Integer> RightData = new ArrayList<Integer>(dataset.subList(dataset.size() / 2, dataset.size()));
dataset = Merge(MergeSort(LeftData), MergeSort(RightData));
}
return dataset;
}

// merge the left and right lists together
static ArrayList<Integer> Merge(ArrayList<Integer> LeftData, ArrayList<Integer> RightData) {
ArrayList<Integer> MergedData = new ArrayList<Integer>();
while (LeftData.size() > 0 || RightData.size() > 0) {
Iterations3++;
if (RightData.size() == 0) {
MergedData.add(LeftData.get(0));
LeftData.remove(0);
} else if (LeftData.size() == 0) {
MergedData.add(RightData.get(0));
RightData.remove(0);
} else if (LeftData.get(0) < RightData.get(0)) {
MergedData.add(LeftData.get(0));
LeftData.remove(0);
} else {
MergedData.add(RightData.get(0));
RightData.remove(0);
}
}
return MergedData;
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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