Linked List Sorting Problem

[Joel Cochran]

I'm trying to sort a list of integers using bubble sort, insertion sort and selection sort and so far it isn't going so hot. I've created my own LinkedList class (singly linked list) and am a little stuck. Here's everything I have so far...

import java.util.Scanner;
import java.io.*;
 
public class sortingTest {
    
    public sortingTest() {}
    
    public static void main(String[] args) throws IOException {
        final String  T1 = "T1.dat", T2 = "T2.dat", T3 = "T3.dat";
        sortingMethods sort = new sortingMethods();
        
        LinkedList bubble_t1, bubble_t2, bubble_t3;
        LinkedList insertion_t1, insertion_t2, insertion_t3;
        LinkedList selection_t1, selection_t2, selection_t3;
        
        LinkedList list_t1 = new LinkedList();   //Original LinkedLists
        LinkedList list_t2 = new LinkedList();
        LinkedList list_t3 = new LinkedList();
        
        initializeList(list_t1, T1);   //Initialize lists
        initializeList(list_t2, T2);
        initializeList(list_t3, T3);
        
        bubble_t1 = new LinkedList(list_t1);   //Initialize all of the remaining lists with
        bubble_t2 = new LinkedList(list_t2);   //their proper files.
        bubble_t3 = new LinkedList(list_t3);
        insertion_t1 = new LinkedList(list_t1);
        insertion_t2 = new LinkedList(list_t2);
        insertion_t3 = new LinkedList(list_t3);
        selection_t1 = new LinkedList(list_t1);
        selection_t2 = new LinkedList(list_t2);
        selection_t3 = new LinkedList(list_t3);
        
        sort.bubbleSort(bubble_t1);
        //sort.insertionSort(insertion_t1);
        //sort.selectionSort(selection_t1);
        //sort.bubbleSort(bubble_t2);
        //sort.insertionSort(insertion_t2);
        //sort.selectionSort(selection_t2);
        //sort.bubbleSort(bubble_t3);
        //sort.insertionSort(insertion_t3);
        //sort.selectionSort(selection_t3);
        
        bubble_t1.print();
    }
    
    
    
    public static void initializeList(LinkedList list, String fileName) throws IOException {
        Scanner scan = new Scanner(new File(fileName));
        while(scan.hasNext()) {
            int number = scan.nextInt();
            list.insert(number);
        }
    }
}

    
public class sortingMethods {
    
    public sortingMethods() {}
    
    
    public void bubbleSort(LinkedList list) {
        if(list.isEmpty())
            System.out.println("List is currently empty.");
        else if (list.size() == 1)
            System.out.println("List is already sorted.");
        else {
            Node current = list.getHead();
            Node counter = current;
            while(counter.getNext().getNext() != null) {
                current = counter;
                while(current.getNext() != null) {
                    if(current.getData() > current.getNext().getData()) {
                        int temp = current.getData();
                        current.setData(current.getNext().getData());
                        current.getNext().setData(temp);
                    }
                    current = current.getNext();
                }
                counter = counter.getNext();
            }
        }
    }
    
    public void selectionSort(LinkedList list) {
        if(list.isEmpty())
            System.out.println("List is currently empty.");
        else if (list.size() == 1)
            System.out.println("List is already sorted.");
        else{}
    }
   /* 
    public void insertionSort(LinkedList list){
        if(list.isEmpty())
            System.out.println("List is currently empty.");
        else if (list.size() == 1)
            System.out.println("List is already sorted.");
        else {
            LinkedList sublist = new LinkedList();
            Node back = null;
            Node newNode = new Node(item);
            Node pointer = list.getHead();
            boolean found = false;
            
            while(pointer != null && !found) {
                if(pointer.getData() > item)
                    found = true;
                else {
                    back = pointer;
                    pointer = pointer.getNext();
                }
            }
            newNode.setNext(pointer);
            if(back == null) {
                head = newNode;
                count++;
            } 
            else {
                back.setNext(newNode);
                count++;
            }
        }
    }*/
}

    
package cs321_assignment1;
 
public class LinkedList {   //Doubly Linked List
    private Node head;
    private int count;
    
    public LinkedList() {
        head = null;
        count = 0;
    }
    
    public LinkedList(LinkedList rhs) {   //Copy constructor
        head = rhs.head;
        count = rhs.count;
    }
    
    public void orderedInsert(int item) {   //Inserts the Node in the right position - Ascending
        Node back = null;
        Node newNode = new Node(item);
        Node pointer = head;
        boolean found = false;
        
        while(pointer != null && !found) {
            if(pointer.getData() > item)
                found = true;
            else {
                back = pointer;
                pointer = pointer.getNext();
            }
        }
        newNode.setNext(pointer);
        if(back == null) {
            head = newNode;
            count++;
        } 
        else {
            back.setNext(newNode);
            count++;
        }
    }
    
    public void insert(int item) {   //Inserts at front of list
        Node newnode = new Node(item);
        if(head == null)
            head = newnode;
        else {
            newnode.setNext(head);
            head = newnode;
        }
        count++;
    }
    
    public void orderedRemove(int item) {   //Searches and removes selected Node
        Node back = null;
        boolean found = false;
        Node pointer = head;
        
        while(pointer != null && !found) {
            if(pointer.getData() == item)
                found = true;
            else {
                back = pointer;
                pointer = pointer.getNext();
            }
        }
        if(found)
            if(back == null) {
            head = pointer.getNext();
            count--;
            } else {
            back.setNext(pointer.getNext());
            count--;
            } else
                System.out.println("Data not found in list.");
    }
    
    public void remove() {   //Removes from front of list
        if(head == null)
            System.out.println("List is currently empty.");
        else {
            Node n = head;
            head = head.getNext();
            n.setNext(null);
            count--;
        }
    }
    
    public boolean isEmpty() {
        if(count == 0)
            return true;
        else
            return false;
    }
    
    public void print() {
        Node current = head;
        while(current != null) {
            System.out.println(current.getData());
            current = current.getNext();
        }
    }
    
    public int size() {return count;}
    
    public Node getHead() {return head;}
    
    public void setHead(Node n) {head = n;}
    
    
    
    
} //End LinkedList class
 

    
package cs321_assignment1;
 
public class Node {
    private int data;
    private Node next;
    
    public Node() {next = null;}
    
    public Node(int d) {
        next = null;
        data = d;
    }
    
    public int getData() {return data;}
    
    public void setData(int newData) {data = newData;}
    
    public Node getNext() {return next;}
    
    public void setNext(Node newNode) {next = newNode;}
}

Ignore the insertionSort method. The bubbleSort methods ALMOST works. For some reason it ignores about half the list and sorts the other half correctly. Any tips/advice on improving my existing code and help on the other sorting methods will be VERY much appreciated. Thanks!!

[Jeanne Boyarsky]

Please don't post the same question in multiple forums. This makes replies harder to follow.