Insertion Sort LinkedList Java

Question

I'm trying to write an Insertion sort for a LinkedList, I have got a working method but it is incredibly slow. Over an hour to add&sort 50,000 elements.

public void insert(Custom c) 
{
    int i = 0;
    for (i = 0; i < list.size(); i++)
    {
        if(list.get(i).compareTo(c) > 0  )
        {
            list.add(i,c);
            return;
        }
    }
    list.add(c);    
}

I know i could use Collections.Sort but for this assignment I am required to write my own LinkedList. I'm not asking for a full solution just some pointers.

Answer 1

First of all, insertion sort on a List is going to be slow (O(N^2)) ... no matter how you do it. But you appear to have implemented it as O(N^3).

Here is your code ... which will be called N times, to add each list element.

public void insert(Entry e) 
{
    int i = 0;
    for (i = 0; i < list.size(); i++)       // HERE #1
    {
        if(list.get(i).compareTo(e) > 0  )  // HERE #2
        {
            list.add(i,e);                  // HERE #3
            return;
        }
    }
    list.add(e);                            // HERE #4   
}

At "HERE #1" we iterate up to M times where M is the current (partial) list length; i.e. O(M). This is inherent in an insertion sort. However, depending on how you implemented the size() method, you could have turned the iteration into a O(M^2) sequence of operations. (The LinkedList.size() method just returns the value of a size variable. No problem here. But if size() counted the elements ... )

At "HERE #2" we have a fetch and a comparison. The comparison (compareTo(...)) is cheap, but the get(i) operation on a linked list involves traversing the list from the beginning. That is an O(M) operation. And since you make the get(i) call O(M) times per insert call, this makes the call O(M^2) and the sort O(N^3).

At "HERE #3" the add(i,e) repeats the list traversal of the previous get(i) call. But that's not so bad because you only execute that add(i,e) call once per insert call. So the overall complexity is not affected.

At "HERE #4" the add() operation could be either O(1) or O(M) depending on how it is implemented. (For LinkedList.add() it is O(1) because the list data structure keeps a reference to the last node of the list.) Either way, overall complexity is not affected.

In short:

• The code at #2 definitely make this an O(N^3) sort.

• The code at #1 could also make it O(N^3) ... but not with the standard LinkedList class.

---

So what to do?

• One approach is to recode the insert operation so that it traverses the list using the next and prev fields, etcetera directly. There should not be calls to any of the "higher level" list operations: size, get(i), add(e) or add(i, e).

  However, if you are implementing this by extending or wrapping LinkedList, this is not an option. Those fields are private.

• If you are extending or wrapping LinkedList, then the solution is to use the listIterator() method to give you a ListIterator, and use that for efficient traversal. The add operation on a ListIterator is O(1).

• If (hypothetically) you were looking for the fastest way to sort a (large) LinkedList, then the solution is to use Collections.sort. Under the covers, that method copies the list contents to an array, does an O(NlogN) sort on the array, and reconstructs the list from the sorted array.

Answer 2

According to this response, you should use ListIterator.add() instead of List.add due to the better performance.

Answer 3

What about using a faster sorting algorithm?

Here is something known as QuickSort. Its way faster then normal sorts for larger data sets. QuickSort has a average case of O(nlogn) while insertion only has a average case of O(n^2). Big difference isn't it?

Sample implementation

QuickSort Class

import java.util.*;

public class QuickSort{


    public static void swap(int A[] , int x, int y){

        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;

    }



    public static int[] QSort(int A[],int L, int U){
        Random randomGenerator = new Random();

        if ( L >= U){
            return A;
        }

        if (L < U) {
            /*                                                                                                                                                                                                                                                                
              Partion the array around the pivot, which is eventually placed                                                                                                                                                                                                  
              in the correct location "p"                                                                                                                                                                                                                                     

            */

            int randomInt = L + randomGenerator.nextInt(U-L);
            swap(A,L,randomInt);
            int T = A[L];
            int p = L;

            for(int i= L+1; i<= U; i++){
                if (T > A[i]){
                    p = p+1;
                    swap(A,p,i);

                }


            }



        /* Recursively call the QSort(int u, int l) function, this deals with                                                                                                                                                                                                 
           the upper pointer first then the lower.                                                                                                                                                                                                                            
        */
            swap(A,L,p);
            QSort(A,p+1,U);
            QSort(A,L, p-1);

        }
        return A;

    }
}

Sample Main

import java.util.*;

public class Main{
    public static void main(String [] args){

        int[] intArray =  {1,3,2,4,56,0,4,2,4,7,80,120,99,9,10,67,101,123,12,-1,-8};

        System.out.printf("Original Array was:\n%s\n\n",Arrays.toString(intArray));

        System.out.printf("Size of Array is: %d\n\n",intArray.length);

        QuickSort.QSort(intArray, 0, intArray.length - 1);
        int num = Integer.parseInt(args[0]);
        System.out.println("The sorted array is:");
        System.out.println(Arrays.toString(intArray));

    }
}

The above example will sort an Int array but you can easily edit it to sort any object(for example Entry in your case). Ill let you figure that out yourself.

Good Luck

Answer 4

list.add(e) and list.get(e) will take o(n) each time they are called. You should avoid to use them when you travel your list.

Instead, if you have to write your own linked list you should keep track of the elements you are traveling. by replacing the operation i++ and get(i) by elem = elem.next or elem = elem.getnext(), (maybe something else depending on how you implemented your linked list). Then you add an element by doing:

elem.next.parent = e;
e.next = elem.next;
elem.next = e;
e.parent = elem; 

here my example works for a doubly linked list and elem represent the element in the linked list you are currently comparing your object you want to add.