Java Answers Forum - Merge sort for Linked lists

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Java Answers Forum
Merge sort for Linked lists

2 replies on 1 page. Most recent reply: Nov 25, 2006 8:21 PM by Matt Gerrans

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 2 replies on 1 page

Jenny G

Posts: 2
Nickname: jenny04
Registered: Mar, 2006

Merge sort for Linked lists

Posted: Nov 24, 2006 8:08 AM

The code I have is meant to read in information from accounts.dat, merge sort it, then output the sorted account into a file called lines.out:

Ive completed the bits which i had to fill in and the program complies ok, but doesnt work when i run it
Heres the program, any suggestions of what is wrong would be grateful.
----------------------------------------------------

import java.io.*;
import java.util.Scanner;
public class SortLinkedList
{

static FileWriter fw;
static BufferedWriter bw;
static PrintWriter outFile;
public static void main(String[] args)throws IOException
{

String line, name;
Scanner fileScanner;
LinearNode list = null;
LinearNode temp;

int accNum, num;
double accBal;
Account1 acc;

fileScanner = new Scanner (new File("accounts.dat"));
fw = new FileWriter ("lines.out");
bw = new BufferedWriter (fw);
outFile = new PrintWriter (bw);

while(fileScanner.hasNext())
{
line = fileScanner.nextLine();
Scanner lineScanner = new Scanner(line);

name = lineScanner.next();
accNum= lineScanner.nextInt();
accBal = lineScanner.nextDouble();

acc = new Account1(name, accNum, accBal);
temp = new LinearNode(acc);
temp.setNext(list);
list = temp;
}

outFile.println("Accounts List");
outFile.println("Number\tName\tBalance");
printList(list);
outFile.prin tln("Number of Accounts " + countList(list));

list = LinkedMergeSort(list);

outFile.println("Accounts List");
outFile.println("Number\tName\tBalance");
printList(list);
outFile.prin tln("Number of Accounts " + countList(list));
outFile.close();
}

public static void printList(LinearNode L)
{
// output the list to the file
LinearNode temp = L;

while (temp != null)
{
outFile.println(temp.getElement());
temp = temp.getNext();
}
}

public static int countList(LinearNode L)
{
// recursive method

if(L==null) return 0;
else return (1 + countList(L.getNext()));
}

public static LinearNode LinkedMergeSort(LinearNode L)
{
if (L.getNext()!=null)
{
LinearNode temp, tail, lowList, highList;
int mid, index;

mid = countList(L)/2;
temp = L;

// get to middle of the list
// by moving temp along

for(int i=1; i {
temp = temp.getNext();
}

// form lowList and highList
// making highlist reference second half
// and unhitching the second half from the first

highList = temp;
lowList = L;
temp = L;

for(int i=1; i {
temp = temp.getNext();
}
temp.setNext(null);

// Sort the lists with recursive calls

lowList = LinkedMergeSort(lowList);
highList = LinkedMergeSort(highList);

L=null;
tail = null;
temp = null;

// Merge lowList and highList into L
// while there are items on both lists
// compare items at start of the two lists
// make temp ref smaller and remove from its list
// put item temp refs onto end of list L

while ((lowList!= null) && (highList != null))
{

if(((Comparable)lowList.getElement()).compareTo(highList.getElement() ) {
temp=lowList;
lowList=lowList.getNext();
}
else
{
temp=highList;
highList=hig hList.getNext();
}
}

if(L==null) L=temp;
else tail.setNext(temp);
tail = temp;
tail.setNext(null);

// connect remainder of lowList or highList to end of L
if(lowList == null)
{
tail.setNext(highList);
}
else
{
tail.setNext(lowList);
}

}
return L;

}
}

-----------------------------------------------------

The code complies but when i go to run it, it says there is problems with line 49 and 100.

Line 49: list = LinkedMergeSort(list);
Line 100: if (L.getNext()!=null)

Vincent O'Sullivan

Posts: 724
Nickname: vincent
Registered: Nov, 2002

Re: Merge sort for Linked lists

Posted: Nov 24, 2006 2:31 PM

As it stands, the code above contains too many errors to compile (including references to classes such as LinearNode and Account1, which you haven't provided).

Until that's sorted, it's not worth anyone's while checking why it won't run.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Merge sort for Linked lists

Posted: Nov 25, 2006 8:21 PM

And, when you do get it compiling, remember to use the java tags when posting, so the code looks readable.

Flat View: This topic has 2 replies on 1 page

Previous Topic

Next Topic


	Web Artima.com