0

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
4
  • I think the line if (list.get(i).compareTo(list.get(i+1)) > 0) { swap(i, i + 1); may be the issue, did you mean j instead of I? Commented Sep 9, 2022 at 22:19
  • Thank you, I overlooked that. Commented Sep 9, 2022 at 23:53
  • If that solved the problem, you might want to delete the question. Commented Sep 10, 2022 at 0:25
  • Questions must not be deleted, instead he can answer his question and mark ✓ so others can learn from it Commented Sep 10, 2022 at 17:42

2 Answers 2

1

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.

Sign up to request clarification or add additional context in comments.

Comments

1

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);
            }
        }
    }
}

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.