java linkedlist string sort algorithm

Question

So, I have several lists of word pairs and I need to sort them in ascending or descending order. The method I'm using right now is the insertion sort algorithm. And this seems to work fine for the smaller lists. But every time I try to sort a large list, it freezes, with no errors. I tried to see what was going on by debugging with printing out "a was swapped for b" and you can see it start working and it slows down and eventually stops like the computer just said, "there's too many, I give up". My question is, is there something wrong with my code, or do I simply need to use a more efficient method, and if so, which one and what would it look like?

for (int j=0; j < wordpair_list.size()-1; j++){
    for (int i=0; i < wordpair_list.size()-1; i++){
        String wordA_1 = wordpair_list.get(i).getWordA();
        String wordA_2 = wordpair_list.get(i+1).getWordA();

        if (wordA_1.compareToIgnoreCase(wordA_2) < 0){
            WordPair temp = wordpair_list.get(i);
            wordpair_list.set(i,wordpair_list.get(i+1));
            wordpair_list.set(i+1, temp);           
        }
    }
}

that's for descending. all i do for ascending is swap the '>' in the if statement to '<'

What number of elements are we talking about? dozens? hundreds? millions? — amit
– amit, Commented Apr 11, 2014 at 7:08
Also, from looking at it briefly - that looks more like a bubble sort than insertion sort to me — amit
– amit, Commented Apr 11, 2014 at 7:12
Some List implementations can be slow being accessed to (maybe are you using Vector?) Since the size of the list does not change, I would implement this logic using arrays (or at the very least, an ArrayList) — SJuan76
– SJuan76, Commented Apr 11, 2014 at 7:13
@amit - thousands. also i apologize if i don't know the difference. still in college and just learned about insertion sort, so that's what i was going for. — StillLearningGuy
– StillLearningGuy, Commented Apr 11, 2014 at 7:15

Abhishek Bansal · Accepted Answer · 2014-04-11 07:30:21Z

1

I think you are performing bubble sort. As others have pointed out, performing get() and set() operations are expensive with linked lists.

I am not conversant with Java, but it appears that you can use ListIterators to carry out bubble sort in O(N^2)

ListIterator listIterator(int index) Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. Throws IndexOutOfBoundsException if the specified index is is out of range (index < 0 || index >= size()).

For bubble sort, you just need to swap the adjacent elements, so you can iterate through the list like an array and keep swapping if needed.

Moreover, you can skip the section of the list that is already sorted. Take a look at a good bubble sort algorithm. http://en.wikipedia.org/wiki/Bubble_sort

answered Apr 11, 2014 at 7:30

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

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

1 Comment

johncip Over a year ago

Yup, the ListIterator allows add and remove from arbitrary places in a LinkedList in constant time (assuming the iterator is already at that position). OP should have used an array though :)

Oleg Estekhin · Accepted Answer · 2014-04-11 07:23:09Z

Besides the fact that insertion sort is already O(N^2) algorithm, the access (both get and set) to the item in the linked list by the item index is O(N) operation, making your code O(N^3), in other words extremely slow.

Basically, you have two options:

copy the linked list into a temp array, sort an array using your algorithm (array access by index is O(1), overall algorithm will stay at O(N^2) (unless you choose a better one), create a new sorted linked list from the array.
use some other algorithm that does not need indexed access (for example, it is actually possible to implement insertion sort without indexed operations because you can swap two adjacent items in the linked list, through you will have to use a linked list implementation where you have direct access to the "previous" and "next" links).

Ivaylo Strandjev · Accepted Answer · 2014-04-11 07:25:38Z

0

First of all this is not insert sort, this is closer to bubble sort. Second, there is nothing wrong with your code, but as expected for this sorting algorithm it is quadratic. Thus for larger input it may take a long time to finish(e.g. for 200 000 elements it may take several minutes).

EDIT: as you are using List the complexity is even higher - up to cubic. As set in a list is not constant. You may try to implement the algorithm with Array to save this added complexity.

edited Apr 11, 2014 at 7:25

answered Apr 11, 2014 at 7:17

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

2 Comments

Abhishek Bansal Over a year ago

It seems more of a bubble sort to me.

Ivaylo Strandjev Over a year ago

@AbhishekBansal argh ... true. I was mislead a bit by the code. Will fix that

Collectives™ on Stack Overflow

java linkedlist string sort algorithm

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related