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.

It's probably because you keep calling list.get(i) which is an O(n) operation. — arshajii
– arshajii, Commented Mar 15, 2014 at 23:25
How often does it get to list.add(e);? If it's happening often you could try comparing e to the last entry first. — MrLore
– MrLore, Commented Mar 15, 2014 at 23:27
@user3424480 It may be worth trying it first anyway, that's still 39,992 less calls to compareTo(). — MrLore
– MrLore, Commented Mar 15, 2014 at 23:31

Stephen C · Accepted Answer · 2014-03-16 01:43:09Z

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.

Community · Accepted Answer · 2017-05-23 10:25:04Z

0

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

edited May 23, 2017 at 10:25

CommunityBot

11 silver badge

answered Mar 15, 2014 at 23:30

oschlueter

2,7081 gold badge28 silver badges52 bronze badges

1 Comment

user3424480 Over a year ago

have added an Iterator in now. Performance vastly improved. 50,000 in around 40 seconds now

SeahawksRdaBest · Accepted Answer · 2014-03-15 23:38:50Z

0

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

edited Mar 15, 2014 at 23:38

answered Mar 15, 2014 at 23:33

SeahawksRdaBest

8865 silver badges18 bronze badges

10 Comments

SeahawksRdaBest Over a year ago

should mention data set has to be sufficiently large however. So you are talking about millions of entries not thousands.

Obicere Over a year ago

This could be for an assignment where a insertion-sort is needed.

SeahawksRdaBest Over a year ago

Yeah could be, but he doesn't mention he's limited to 50,000 elements... maybe he just gave up cause 50,000 was taking too long

Stephen C Over a year ago

@SeahawksRdaBest - it depends on the JVM version. In Java 7, it is a form of Quicksort for primitives and TimSort for objects - stackoverflow.com/questions/4018332/…. But the point is that the algorithms are better than O(N^2).

user3424480 Over a year ago

@StephenC I'm using my own Insertion sort again in my Arrays implementation.

|

mrudelle · Accepted Answer · 2014-03-15 23:44:18Z

0

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.

edited Mar 15, 2014 at 23:44

answered Mar 15, 2014 at 23:39

mrudelle

1531 gold badge1 silver badge7 bronze badges

Collectives™ on Stack Overflow

Insertion Sort LinkedList Java

4 Answers 4

Comments

1 Comment

Sample implementation

QuickSort Class

Sample Main

10 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Sample implementation

QuickSort Class

Sample Main

10 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related