Alright guys I am lost. I thought that I had this correct but I have done something terribly wrong. The bubble sort simply spits out the orginal string and the merge sort goes on forever and the bucket sort doesn't seem to do anything. Please help!
package com.shadowconcept.mcdougal;
import java.io.*;
public class Sort {
public static void main(String[] args) {
/* Retrieves the filename of dataset from the command-line arguments */
if (args.length != 1) {
System.err.println("Usage:java Sort filename.txt");
System.exit(1);
}
/* Reading data from the file system */
try {
int[] data = null;
String line;
FileReader input = new FileReader(args[0]);
BufferedReader bufRead = new BufferedReader(input);
line = bufRead.readLine();
while (line != null) {
if (line.length() > 0) {
String[] tokens = line.split(" ");
data = concat(data, str2int(tokens));
}
line = bufRead.readLine();
}
bufRead.close();
/* Create an instance of Sort class */
Sort s = new Sort();
/* Perform bubble sort on dataset and display the result */
int bubblesorted[] = s.bubble(data);
s.dispList(bubblesorted);
/* Perform merge sort on dataset and display the result */
//s.dispList(s.merge(data));
/* Perform bucket sort on dataset and display the result */
s.dispList(s.bucket(data));
} catch (IOException e) {
e.printStackTrace();
} // end of try ... catch
} // end of main
public static int[] bubble(int[] list) {
int[] sortedList = null;
System.out.println("Run bubble sort");
int i = list.length ;
for (int pass=1; pass < i; pass++) {
// count how many passes through the array
for (int j=0; i < i-pass; i++) {
if (list[j] > list[j+1]) {
// This swaps the elements in the array around
int temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
sortedList = list;
return sortedList;
}
public static int[] merge(int[] list)
{
System.out.println("Run merge sort");
if(list.length == 0)
return list;
int list1Size = list.length/2; //this truncates any remainder.
int list2Size = list.length/2 + list.length%2;
int[] firsthalf = new int[list1Size ];
int[] secondhalf = new int[list2Size ];
//using the listSizes, and the list parameter, fill the two arrays.
int[] result1 = merge(firsthalf );
int[] result2 = merge(secondhalf );
int index1 = 0;
int index2 = 0;
int[] sortedList = new int[list.length];
int i = 0;
while(index1 < result1.length && index2 < result2.length)
{
//if one of the two arrays has already been copied completely, then grab the next item from the other.
if(index1 == result1.length || index2 == result2.length)
{
if(index1 == result1.length)
{
sortedList[i] = result2[index2];
index2++;
}
else
{
sortedList[i] = result1[index1];
index1++;
}
}
else
{
//otherwise, we need to figure out which item is smaller, and move that one to the next empty array position.
if(result1[index1] < result2[index2])
{
sortedList[i] = result1[index1];
index1++;
}
else
{
sortedList[i] = result2[index2];
index2++;
}
}
i++;
}
return sortedList;
}
public static int[] bucket(int[] list) {
int[] sortedList = new int[list.length];
if(list.length > 0)
{
int max = 0;
int min = list[0];
//loop through and grab max and min values
for(int i=0; i<list.length; i++)
{
if(list[i] < min)
min = list[i];
if(list[i] > max)
max = list[i];
}
int step = (max - min) / 5;
if((max - min) % 5 != 0)
step = step + 1;
int[][] buckets = new int[5][];
//bucket allocation
for(int i=0; i< list.length;i++)
{
int bucketIndex = list[i]/step;
if(list[i] == max)
bucketIndex--;
buckets[bucketIndex] = concat(buckets[bucketIndex], list);
}
//sort the buckets and throw then into the sortedList array.
for(int i=0; i<5; i++)
{
int[] temp = bubble(buckets[i]);
sortedList = concat(sortedList, temp);
}
}
return sortedList;
}
/* The dispList will display all elements in the list */
public static void dispList(int[] list) {
for (int i = 0 ; i < list.length ; i++) {
System.out.print(list[i] + " ");
}
System.out.print("\n");
} // end of dispList
public static int[] concat(int[] A, int[]B) {
if (A != null && B != null) {
int[] C = new int[A.length + B.length];
System.arraycopy(A, 0, C, 0, A.length);
System.arraycopy(B, 0, C, A.length, B.length);
return C;
} else if (A != null) {
return A;
} else if (B != null) {
return B;
}
return null;
}
public static int[] str2int(String[] A) {
int[] B = new int[A.length];
for (int i=0 ; i < A.length ; i++) {
B[i] = Integer.parseInt(A[i]);
}
return B;
}
} // end of Sort class
These is the numbers that I am sorting. They are in the file 100.txt
63 31 37 94 41 64 72 70 40 33 9 38 84 15 32 91 53 7 96 5 49 41 65 83 37 11 39 51 43 52 99 46 91 59 95 4 10 32 53 31 90 59 70 56 69 62 19 38 27 34 20 23 60 84 36 8 96 23 40 42 34 9 100 95 74 14 86 89 38 33 72 8 59 56 13 36 79 19 73 67 60 40 23 89 79 54 68 19 71 57 61 75 39 91 97 90 48 71 83 61
Linear Mode
