Linked List Sorting Problems

[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!!

[Jeff Storey]

I think you're on the right track, but a couple of things I see here:

First, as far as general Java practices (and most object-oriented languages), you should start all class names with a capital letter, such as SortingMethods or SortingTest, not how you have it (although you did it correctly with some classes).

Another point is about your LinkedList class. I'm not sure this would be classified as a doubly LinkedList. A doubly LinkedList has pointers to the next and previous nodes (hence a doubly linked list), but your Node only points to the next node, which would make it a singly, or just a regular LinkedList.

To help make your code a little easier to read, look at methods like your LinkedList isEmpty method. Instead of "if(count...)", just do something like "return count == 0;" without the if statements.

Now, as for the bubble sort algorithm. I think the reason it's not working properly is because you don't pass through the whole list on each iteration. You should start with the first element of the list on each pass through the list and stop once you get through the entire list without doing any swaps. Think of this list: 2, 4, 1. The way your algorithm is implemented, it will swap the 4 and the 1 and will leave the list 2,1,4, but since you never go back to the beginning of the list, you'll never swap the 2 and the 1. Does that make sense?

Now some last Java points, and this is probably somewhat beyond where you are now because it looks like you're in a basic Java class. Typically, you would want to have an interface called Sorter (or something like this). The sorter would have a method called sort(LinkedList l). You could then have a couple of different implementations of it, such as BubbleSorter, InsertionSorter, etc. Then you would have a method called sortList(LinkedList l, Sorter s) that would simply call s.sort(l), and this would sort the list based on the sorter you passed in. But, the method wouldn't need to know the type of sorter. I know I've inlined a lot of code here, but hopefully that gives you some ideas.

Hopefully I haven't thrown too much at you, but I hope this helps. Feel free to ask more questions if you'd like.

Jeff

[Joel Cochran]

Yes, I still have questions
How can I make sure that it checks each one? I've added a boolean variable to check whether a swap is made or not, so I've got that covered, but I don't know how to restart or continue from the correct place.

[Joel Cochran]

Okay! I've changed it a bit more, but for some reason I still have one larger int stuck at the front of the list whenever I print it out.

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.getFirst();
            Node counter = current;
            boolean exchangeMade = true;
            while(counter.getNext().getNext() != null && exchangeMade) {
                current = list.getFirst();
                exchangeMade = false;
                while(current.getNext() != null) {
                    if(current.getData() > current.getNext().getData()) {
                        int temp = current.getData();
                        current.setData(current.getNext().getData());
                        current.getNext().setData(temp);
                        exchangeMade = true;
                    }
                    current = current.getNext();
                }
                counter = counter.getNext();
            }
            }
        }      
 

The output looks like this:
8409
0
0
12
63
97
636
682
773
847
905
933
1258
1338
1826
1992
2543
2868
3026
3221
3287
3671
3796
3800
3829
3945
4420
4607
4782
4950
5242
5337
5898
6091
6154
6160
6216
6598
7089
7154
7203
7515
7542
7654
8147
8149
8511
8687
8907
8984
8997
9976

[Jeff Storey]

Try something like this...

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.getFirst();
            boolean exchangeMade = true;
            while(exchangeMade) {
                current = list.getFirst();
                exchangeMade = false;
 
                // Start at the beginning and loop over all elements                           
                while(current != null) {
                    if(current.getData() > current.getNext().getData()) {
                        int temp = current.getData();
                        current.setData(current.getNext().getData());
                        current.getNext().setData(temp);
                        exchangeMade = true;
                    }
                    current = current.getNext();
                }
                
            }
            }
        }      
 

[ October 01, 2007: Message edited by: Jeff Storey ]