I'm doing a Java programming assignment which involves bubble sorting a .dat file BetelgeuseNames.dat with strings in it alphabetically. My AP Computer Science A teacher told me my code is correct, but it still gives the wrong output.
There are three classes called BubbleSort, BubbleSortTimer, and StopWatch. The program runs from BubbleSortTimer.
BubbleSort:
import java.util.ArrayList;
import javax.swing.JOptionPane;
import java.io.FileWriter;
import java.io.IOException;
public class BubbleSort {
// Private instance variables:
private ArrayList<String> list;
private int number;
public BubbleSort(ArrayList<String> a_list) {
list = a_list;
}
public void swap(int first, int second) {
String temp1 = list.get(first);
String temp2 = list.get(second);
list.set(first, temp2);
list.set(second, temp1);
}
public int getNumber() {
String numStr;
numStr = JOptionPane.showInputDialog("How many names do you want to sort?");
number = Integer.parseInt(numStr);
return number;
}
public void printSorted() {
try {
FileWriter writer = new FileWriter("sorted.dat");
for (int i = 0; i < number; i ) {
writer.write(list.get(i) "\n");
}
writer.close();
} catch (IOException exception) {
System.out.println("Error processing file: " exception);
}
}
public void bubbleSort() {
for (int i = 0; i < number; i ) {
for (int j = 0; j < number - i - 1; j ) {
if (list.get(i).compareTo(list.get(i 1)) > 0) {
swap(i, i 1);
}
}
}
} // End method
}
BubbleSortTimer:
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.FileReader;
import javax.swing.JOptionPane;
import java.io.IOException;
public class BubbleSortTimer {
private ArrayList<String> list = new ArrayList<String>();
public void readNames() {
try {
FileReader reader = new FileReader("BetelgeuseNames.dat");
BufferedReader in = new BufferedReader(reader);
boolean done = false;
String name;
while (done == false) {
name = in.readLine();
if (name == null) {
done = true;
} else {
list.add(name);
}
}
reader.close();
} catch (IOException exception) {
System.out.println("Error processing file: " exception);
}
} // End method
public void runSort() {
readNames();
StopWatch timer = new StopWatch();
BubbleSort sorter = new BubbleSort(list);
int number = sorter.getNumber();
timer.start();
sorter.bubbleSort();
timer.stop();
sorter.printSorted();
String msg = "Number of names sorted: " number "\nMilliseconds required to sort: " timer.getElapsedTime() "\nOutput file is \"sorted.dat\"";
JOptionPane.showMessageDialog(null, msg);
}
public static void main(String[] args) {
BubbleSortTimer bubble = new BubbleSortTimer();
bubble.runSort();
}
}
StopWatch:
/**
* A stopwatch accumulates time when it is running. You can
* repeatedly start and stop the stopwatch. You can use a
* stopwatch to measure the running time of a program.
* from section 18.2 of Horstmann's CCJ
*/
public class StopWatch {
/**
* Constructs a stopwatch that is in the stopped state
* and has no time accumulated.
*/
public StopWatch() {
reset();
}
/**
* Starts the stopwatch. Times starts accumulating now.
*/
public void start() {
if (isRunning) return;
isRunning = true;
startTime = System.currentTimeMillis();
}
/**
* Stops the stopwatch. Time stops accumulating and is
* added to the elapsed time.
*/
public void stop() {
if (!isRunning) return;
isRunning = false;
long endTime = System.currentTimeMillis();
elapsedTime = elapsedTime endTime - startTime;
}
/**
* Returns the total elapsed time.
@return the total elapsed time
*/
public long getElapsedTime() {
if (isRunning) {
long endTime = System.currentTimeMillis();
elapsedTime = elapsedTime endTime - startTime;
startTime = endTime;
}
return elapsedTime;
}
/**
* Stops the watch and resets the elapsed time to 0.
*/
public void reset() {
elapsedTime = 0;
isRunning = false;
}
private long elapsedTime;
private long startTime;
private boolean isRunning;
}
Input:
Moewm
Bmlzvltcso
Aqxjor
Wwgjie
Qqqtpivd
Xgyhaerv
Wqpjwdvxjq
Ecsfnow
Zlptuqxctt
Jhtprwvopk
Expected Output:
Aqxjor
Bmlzvltcso
Ecsfnow
Jhtprwvopk
Moewm
Qqqtpivd
Wqpjwdvxjq
Wwgjie
Xgyhaerv
Zlptuqxctt
Actual Output:
Bmlzvltcso
Aqxjor
Moewm
Qqqtpivd
Wwgjie
Wqpjwdvxjq
Ecsfnow
Xgyhaerv
Jhtprwvopk
Zlptuqxctt
CodePudding user response:
This is how Android did (binary) sorting (edited to fix this situation):
public void binarySort() {
int lo = 0; // sort start
for (int start=lo ; start < number; start ) {
String pivot = list.get(start);
// Set left (and right) to the index where list.get(start) (pivot) belongs
int left = 0;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left].
* pivot < all in [right, start].
*/
while (left < right) {
int mid = (left right) >>> 1;
if (pivot.compareTo(list.get(mid)) < 0)
right = mid;
else
left = mid 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left] and
* pivot < all in [left, start], so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just reshifter in default case
switch (n) {
case 2: list.set(left 2,list.get(left 1));
case 1: list.set(left 1,list.get(left));
break;
default:
if(n>0){
list.add(left,list.remove(left n));
}
}
list.set(left,pivot);
}
}
This is how you can do (bubble) sorting:
public void bubbleSort() {
for (int i = 0; i < number; i ) {
for (int j = i 1; j < number; j ) {
if (list.get(i).compareTo(list.get(j)) > 0) {
swap(i, j);
}
}
}
}
BUBBLE SORTING V/S BINARY SORTING:
OFF TOPIC: As you can compare above, bubble sorting is easier to code/read/understand and is also faster as compared to binary sorting, because binary sorting (actually) uses array recreation many times which ofcourse takes more time compared to swap.
CodePudding user response:
Because there is a problem with your bubbleSort()
method. Please try this way.
public void bubbleSort() {
for (int i = 0; i < number; i ) {
for (int j = 1; j < number - i; j ) {
if (list.get(j - 1).compareTo(list.get(j)) > 0) {
swap(j - 1, j);
}
}
}
}