I'm not sure where to start, but this is messy. Basically I need to write an Insertion Sort method for singly linked list - which causes enough problems, because usually for Insertion Sort - you're supposed to go through array/list elements backwards - which implementing into a singly linked list seems pointless, because the point of it - is that you're only capable of going forwards in the list and in addition to that -> I need to execute "swap" operations externally, which I do not completely understand how to perform that while using list structure.
This is my ArrayClass and Swap method that I used:
class MyFileArray : DataArray
{
public MyFileArray(string filename, int n, int seed)
{
double[] data = new double[n];
length = n;
Random rand = new Random(seed);
for (int i = 0; i < length; i++)
{
data[i] = rand.NextDouble();
}
if (File.Exists(filename)) File.Delete(filename);
try
{
using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
FileMode.Create)))
{
for (int j = 0; j < length; j++)
writer.Write(data[j]);
}
}
catch (IOException ex)
{
Console.WriteLine(ex.ToString());
}
}
public FileStream fs { get; set; }
public override double this[int index]
{
get
{
Byte[] data = new Byte[8];
fs.Seek(8 * index, SeekOrigin.Begin);
fs.Read(data, 0, 8);
double result = BitConverter.ToDouble(data, 0);
return result;
}
}
public override void Swap(int j, double a)
{
Byte[] data = new Byte[16];
BitConverter.GetBytes(a).CopyTo(data, 0);
fs.Seek(8 * (j + 1), SeekOrigin.Begin);
fs.Write(data, 0, 8);
}
}
And this is my Insertion Sort for array:
public static void InsertionSort(DataArray items)
{
double key;
int j;
for (int i = 1; i < items.Length; i++)
{
key = items[i];
j = i - 1;
while (j >= 0 && items[j] > key)
{
items.Swap(j, items[j]);
j = j - 1;
}
items.Swap(j, key);
}
}
Now I somehow have to do the same exact thing - however using Singly Linked List, I'm given this kind of class to work with (allowed to make changes):
class MyFileList : DataList
{
int prevNode;
int currentNode;
int nextNode;
public MyFileList(string filename, int n, int seed)
{
length = n;
Random rand = new Random(seed);
if (File.Exists(filename)) File.Delete(filename);
try
{
using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
FileMode.Create)))
{
writer.Write(4);
for (int j = 0; j < length; j++)
{
writer.Write(rand.NextDouble());
writer.Write((j + 1) * 12 + 4);
}
}
}
catch (IOException ex)
{
Console.WriteLine(ex.ToString());
}
}
public FileStream fs { get; set; }
public override double Head()
{
Byte[] data = new Byte[12];
fs.Seek(0, SeekOrigin.Begin);
fs.Read(data, 0, 4);
currentNode = BitConverter.ToInt32(data, 0);
prevNode = -1;
fs.Seek(currentNode, SeekOrigin.Begin);
fs.Read(data, 0, 12);
double result = BitConverter.ToDouble(data, 0);
nextNode = BitConverter.ToInt32(data, 8);
return result;
}
public override double Next()
{
Byte[] data = new Byte[12];
fs.Seek(nextNode, SeekOrigin.Begin);
fs.Read(data, 0, 12);
prevNode = currentNode;
currentNode = nextNode;
double result = BitConverter.ToDouble(data, 0);
nextNode = BitConverter.ToInt32(data, 8);
return result;
}
To be completely honest - I'm not sure neither how I'm supposed to implement Insertion Sort nor How then translate it into an external sort. I've used this code for not external sorting previously:
public override void InsertionSort()
{
sorted = null;
MyLinkedListNode current = headNode;
while (current != null)
{
MyLinkedListNode next = current.nextNode;
sortedInsert(current);
current = next;
}
headNode = sorted;
}
void sortedInsert(MyLinkedListNode newnode)
{
if (sorted == null || sorted.data >= newnode.data)
{
newnode.nextNode = sorted;
sorted = newnode;
}
else
{
MyLinkedListNode current = sorted;
while (current.nextNode != null && current.nextNode.data < newnode.data)
{
current = current.nextNode;
}
newnode.nextNode = current.nextNode;
current.nextNode = newnode;
}
}
So if someone could maybe give some kind of tips/explanations - or maybe if you have ever tried this - code examples how to solve this kind of problem, would be appreciated!
I actually have solved this fairly recently.
Here's the code sample that you can play around with, it should work out of the box.
public class SortLinkedList {
public static class LinkListNode {
private Integer value;
LinkListNode nextNode;
public LinkListNode(Integer value, LinkListNode nextNode) {
this.value = value;
this.nextNode = nextNode;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public LinkListNode getNextNode() {
return nextNode;
}
public void setNextNode(LinkListNode nextNode) {
this.nextNode = nextNode;
}
@Override
public String toString() {
return this.value.toString();
}
}
public static void main(String...args) {
LinkListNode f = new LinkListNode(12, null);
LinkListNode e = new LinkListNode(11, f);
LinkListNode c = new LinkListNode(13, e);
LinkListNode b = new LinkListNode(1, c);
LinkListNode a = new LinkListNode(5, b);
print(sort(a));
}
public static void print(LinkListNode aList) {
LinkListNode iterator = aList;
while (iterator != null) {
System.out.println(iterator.getValue());
iterator = iterator.getNextNode();
}
}
public static LinkListNode sort(LinkListNode aList){
LinkListNode head = new LinkListNode(null, aList);
LinkListNode fringePtr = aList.getNextNode();
LinkListNode ptrBeforeFringe = aList;
LinkListNode findPtr;
LinkListNode prev;
while(fringePtr != null) {
Integer valueToInsert = fringePtr.getValue();
findPtr = head.getNextNode();
prev = head;
while(findPtr != fringePtr) {
System.out.println("fringe=" + fringePtr);
System.out.println(findPtr);
if (valueToInsert <= findPtr.getValue()) {
LinkListNode tmpNode = fringePtr.getNextNode();
fringePtr.setNextNode(findPtr);
prev.setNextNode(fringePtr);
ptrBeforeFringe.setNextNode(tmpNode);
fringePtr = ptrBeforeFringe;
break;
}
findPtr = findPtr.getNextNode();
prev = prev.getNextNode();
}
fringePtr = fringePtr.getNextNode();
if (ptrBeforeFringe.getNextNode() != fringePtr) {
ptrBeforeFringe = ptrBeforeFringe.getNextNode();
}
}
return head.getNextNode();
}
}
From a high level, what you are doing is you are keeping track of a fringe ptr, and you are inserting a node s.t. the it is in the correct spot in the corresponding sublist.
For instance, suppose I have this LL.
3->2->5->4
The first iteration, I have fringePtr at 2, and I want to insert 2 somewhere in the sublist that's before the fringe ptr, so I basically traverse starting from head going to the fringe ptr until the value is less than the current value. I also have a previous keeping track of the previous ptr (to account for null, I have a sentinel node at the start of my traversal so I can insert it at the head).
Then, when I see that it's less than the current, I know I need to insert it next to the previous, so I have to:
Then, to continue, you just advance your fringe ptr and try again, basically building up a sublist that is sorted as you move along until fringe hits the end.
i.e. the iterations will look like
1. 3->2->5->4
^
2. 2->3->5->4
^
3. 2->3->5->4
^
4. 2->3->4->5 FIN.