CODEWITHSUNDEEP
csortinglinked-list
Bri
Bri

Reputation: 739

Linked list insertion sort

I'm not very advanced in the sorting part of programming yet, so I was looking for some help with my algorithm.

void sortList()
{
    Item_PTR tmpNxt = current->nextItem;
    Item_PTR tmpPTR = current;
    int a, tmp;

    while(tmpNxt != NULL)
    {   
        a = tmpPTR->value;
        while(tmpNxt != tmpPTR && tmpNxt->value < a)
        {
            tmp = a;
            tmpPTR->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPTR = tmpPTR->nextItem;
        }
        tmpPTR = current;   
        tmpNxt = tmpNxt->nextItem;
    }

}

The list state before sorting: 9 8 7 6 5 4 3 2 1 after sorting: 1 9 8 7 6 5 4 3 2

I'm not sure why...I've played computer a lot on paper and I feel like it should work...but maybe other eyes will spot the problem.

Current is a global pointer that will always have the location of the first/ top element in the list.

Upvotes: 2

Views: 9607

Answers (3)

Dheeraj Sachan
Dheeraj Sachan

Reputation: 4125

         **Java code for insertion sort of linked list**





    package LinkedList;

/**
 * Created by dheeraj on 5/1/15.
 */
public class InsertionSortLinkedList {

    private static final class Node {
        int value;
        Node next;

        public Node(int d) {
            value = d;
            next = null;
        }
    }

    private Node root;
    private Node sortedHead;

    private void addData(int data) {
        if (root == null) {
            root = new Node(data);
        } else {
            Node temp = new Node(data);
            temp.next = root;
            root = temp;
        }
    }

    private void printList() {
        Node temp = root;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    private void printSortedList() {
        Node temp = sortedHead;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    private void insertionSort() {
        Node outer = root;
        Node resultRoot = null;
        if (outer == null) {
            return;
        }
        while (outer != null) {
            if (resultRoot == null) {
                //System.out.println("null");
                resultRoot = new Node(outer.value);
            } else {
                Node t = resultRoot;
                if (outer.value < t.value) {
                    //current outer is smallest
                    //System.out.println("smallest");
                    Node temp = new Node(outer.value);
                    temp.next = t;
                    resultRoot = temp;
                } else {
                    boolean broken = false;
                    while (t.next != null) {
                        if (t.value < outer.value && outer.value <= t.next.value) {
                            Node temp = new Node(outer.value);
                            temp.next = t.next;
                            t.next = temp;
                            broken = true;
                            //System.out.println("middle");
                            break;
                        }
                        //
                        t = t.next;
                    }
                    if (!broken) {
                        //current outer is greatest
                        //System.out.println("largest");
                        t.next = new Node(outer.value);
                    }
                }
            }
            outer = outer.next;
        }
        sortedHead = resultRoot;
    }

    public static void main(String[] args) {
        InsertionSortLinkedList insertionSortLinkedList = new InsertionSortLinkedList();
        insertionSortLinkedList.addData(5);
        insertionSortLinkedList.addData(30);
        insertionSortLinkedList.addData(1);
        insertionSortLinkedList.addData(18);
        insertionSortLinkedList.addData(19);

        insertionSortLinkedList.printList();
        insertionSortLinkedList.insertionSort();
        insertionSortLinkedList.printSortedList();
    }
}

Upvotes: 0

nkongara
nkongara

Reputation: 1229

In addition to the changes suggested by @Arun Saha, there seems to be some logical mistake (not updating a value after swapping), that's why the list os not even printing in sorted order even inside the sort function. Following code should solve that.

void sortList()
{
    Item_PTR tmpNxt = current->nextItem;
    Item_PTR tmpPTR = current;

    while(tmpNxt != NULL)
    {   
        while(tmpNxt != tmpPTR && tmpNxt->value < tmpPTR->value)
        {
            int tmp = tmpPTR->value;
            tmpPTR->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPTR = tmpPTR->nextItem;
        }
        tmpPTR = current;   
        tmpNxt = tmpNxt->nextItem;
    }

}

Upvotes: 1

Arun
Arun

Reputation: 20383

This is because the function sortList() is not changing current, the "global" variable denoting the list head.

Please don't use a global variable, and certainly not for a linked list head. (What will you do when you need two lists?)

I would redesign the sortList() function to either one of the following:

/* sort the list pointed to by phead and return the new head after sorting */
Item_PTR sortList( Item_PTR phead );

/* sort the list pointed to by *pphead */
void sortList( Item_PTR * pphead );

Also, make yourself familiar (even if you can't use them in the immediate project) to the interface of C++ Standard Library for lists, std::list link

Upvotes: 0

Related Questions