Joel Cochran

I'm trying to create 3 different sorting methods (bubble, selection, insertion) that sorts the data in a linked list (custom made). I'm having big time problems with the selection and insertion. I've seen how to do this with arrays, but I just can't seem to make the swap to linked list. I've managed to get the bubble sort to work, but can't seem to get the other two (in fact, I haven't got anything for insertion yet). Here's what I have so far...
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; Node counter = list.getFirst(); boolean exchangeMade = true; int iterationsINNER = 1, iterationsOUTER = 1, swaps = 0, comparisons = 1; while(counter.getNext().getNext() != null && exchangeMade) { current = list.getFirst(); exchangeMade = false; iterationsOUTER++; 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; swaps++; comparisons++; } current = current.getNext(); iterationsINNER++; } counter = counter.getNext(); } System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER); } } public void selectionSort(LinkedList list) { int iterationsINNER = 1, iterationsOUTER = 1, swaps = 0, comparisons = 1; if(list.isEmpty()) System.out.println("List is currently empty."); else if (list.size() == 1) System.out.println("List is already sorted."); else { Node pointer = list.getFirst(); Node current; boolean swapMade = false; int temp = 0; while (pointer.getNext() != null) { current = pointer; iterationsOUTER++; while (current.getNext() != null) { comparisons++; if(current.getNext().getData() < pointer.getData()) { temp = pointer.getData(); swapMade = true; } current = current.getNext(); } if(swapMade) { pointer.setData(current.getData()); current.setData(temp); } pointer = pointer.getNext(); } System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER); } } 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{} }

Any ideas on what's wrong with the selection sort, and any hints for the insertion? Thanks for all your help!

I need to create a program that creates a Pascal's Triangle based on a given n value, and place it into a 2D Array, and print it to the screen. I've been having a little trouble with my methods. For example, if n = 5 and k = 3, then the output should be like:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

public int pascalRecursive(int height, int width) { int[][] doubleArray = new int[height][height]; if(height==width || width==0) return 1; else return pascalRecursive(height-1,width)+pascalRecursive(height-1,width-1); } public void pascalNonRecursive(int height) { int[][] doubleArray = new int[height][height]; for(int k=0; k<height; k++){ for(int r=0; r<k; r++) { doubleArray[r][k] = ((factorial(k) / ((factorial(r) * factorial(k - r))))); System.out.print(doubleArray[r][k]); } } }

PascalArray test = new PascalArray();
test.pascalNonRecursive(5); //GIVES ME 1121331464 as output
System.out.print(test.pascalRecursive(4, 2); //GIVES ME 6 as output

How can I fix (and refine) my code? I obviously need a lot of help, and I will really appreciate anything you give me. Thanks a lot!

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

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.

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

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