Linked list insertion sort

Question

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.

Do you mean "9 8 7 6 5 4 3 2 1" is the state of the list before sorting and "1 9 8 7 6 5 4 3 2" the state after sorting? — Peter G.
– Peter G., Commented Oct 10, 2010 at 17:34
Use gdb: gnu.org/software/gdb It's a command line debugger, and if you're on linux it's probably already installed. — David Brown
– David Brown, Commented Oct 10, 2010 at 17:50

nkongara · Accepted Answer · 2013-04-14 04:13:12Z

1

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;
    }

}

answered Apr 14, 2013 at 4:13

nkongara

1,2298 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Arun · Accepted Answer · 2010-10-10 18:33:12Z

0

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

edited Oct 10, 2010 at 18:33

answered Oct 10, 2010 at 17:48

Arun

20.6k12 gold badges54 silver badges61 bronze badges

2 Comments

Bri Over a year ago

I can't use the library ;) because it is a special project. I'm using tmpPTR to compare all numbers up to tmpNxt. All I'm doing with current is using it to reset the tmpPTR to the top of the list so it can compare all up to the tmpNxt.

Arun Over a year ago

Yes, I figured that, hence I said make yourself familiar :-). Some more suggestions: (1) Write a function to print, say printList(), the contents of the list. (2) use sortList for all combinations of three-element lists [i.e. {1 2 3}, {1 3 2}, {2 1 3} ..} (3) Call printList() both before and after the call to sortList(). Important: Whenever the first element in the list is not the minimum one, its position after sorting is required to change, but unless current is updated, that change won't come into effect.

Dheeraj Sachan · Accepted Answer · 2015-01-05 19:16:00Z

         **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();
    }
}

Collectives™ on Stack Overflow

Linked list insertion sort

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related