For-loop is executed only once?

Question

I'm implementing Insertionsort for university. My code works in theory, but my for-loop is executed only once instead of books.size() (which is 5, I've tested that). I tried it using the number 5, but it won't work and I'm kind of desperate because I can't seem to find the error.

Here is my code:

    static void sort(LinkedList<Book> books)
    {
        int i;
        for ( i = 0; i < books.size(); i++)
        {
            Book temp = books.get(i);
            books.remove(i);
            for (int j = 0; j < books.size(); j++) {
                if (books.get(j).compareTo(temp) > 0) {
                    books.add(j, temp);
                    return;
                }
            }
            books.add(temp);
        }
    }

The compareTo function of the Book-Class looks like the following:

public int compareTo(Book other)
{
    int iAutor = autor.compareTo(other.getAutor());

    if (iAutor != 0)
        return iAutor;
    else
    {
        int iTitel = titel.compareTo(other.getTitel());

        if (iTitel != 0)
            return iTitel;
        else
        {
            if (this.auflage < other.getAuflage())
                return -1;
            else if (this.auflage > other.getAuflage())
                return 1;
            else
                return 0;
        }
    }
}

Am I simply blind?

I guess you checked that the compare function does bit return a value greater zero in the first iteration ? — Raven, Dec 06 '15 at 16:43
@Sparta Well, that happens when you code tired .__. You're right, that's it. But if I exchange it with a `break` it adds every entry twice. Can I do something about it without outsourcing it in a seperate `insert` function? — Valentin, Dec 06 '15 at 16:45
@Valentin explain to us what you are trying to achieve. We might even suggest you some logic insights.. — Mohammed Aouf Zouag, Dec 06 '15 at 16:47
@Sparta I'm trying to do Insertionsort in a `LinkedList`. Therefore I wrote a function to compare Books in the Books class. I now need to sort a list of books. Therefore I save the first entry as a temp value, then I remove it from the list. I now gor through the list from right to left and see if it is greater than the last. If it is, I add it to the list. — Valentin, Dec 06 '15 at 16:50
Apart from what's been said already, your loops don't look right. Try righting down how the insertion sort algorithm works in plain language. Visualize it in your mind. Then, and only then, put it into code. You'll see where you went wrong. (As a hint, consider that you have two sections in your list: a sorted one and an unsorted one. Each time through your outer loop, take one element from the unsorted section and insert it into the correct place in the sorted section.) — Klitos Kyriacou, Dec 06 '15 at 16:56

score 0 · Accepted Answer · answered Dec 06 '15 at 16:49

0

You need to swap return for break and fix the logic to avoid adding the book twice. There may be more elegant ways than this, but it should work:

    int i;
    for ( i = 0; i < books.size(); i++)
    {
        Book temp = books.get(i);
        books.remove(i);
        bool added = false;
        for (int j = 0; j < books.size(); j++) {
            if (books.get(j).compareTo(temp) > 0) {
                books.add(j, temp);
                added = true;
                break;
            }
        }
        if (!added) {
            books.add(temp);
        }
    }

answered Dec 06 '15 at 16:49

swilson

471
4
9

Works fine now, thank you :) Only problem is that I still have a problem with my `compareTo` as it seems, because the output is: Eins, Abraham, 1. Auflage Eins, Bebraham, 2. Auflage Zwei, Bebraham, 2. Auflage Eins, Bebraham, 3. Auflage Drei, Zebraham, 3. Auflage Which is correct but for the fourth entry ._. – Valentin Dec 06 '15 at 17:00
I would guess that's because you're modifying the collection as you iterate: since the order gets mooved but you are inspecting each index one at a time, you may not compare enough pairs to sort properly. Instead (and maybe this is the real answer) you should implement a Comparator (using your compareTo method) and use Collections.sort(), which is easier overall anyway. – swilson Dec 06 '15 at 18:27

score 0 · Answer 2 · answered Dec 06 '15 at 19:42

Well, I found out how to solve it, just if someone has the same problem (don't think that will happen, but it's a good habit I hope).

As @Klitos Kyriacou pointed out right, I had a twist in my thoughts about the process of Insertionsorting.

The solution is changing the loops in the following:

     static void sort(LinkedList<Book> books) {

    Book temp;
    for (int counter = 0; counter < books.size(); counter++) {
        temp = books.get(counter);

        for (int position = 0; position < counter; position++)
        {
            if (temp.compareTo(books.get(position)) < 0)
            {
                books.remove(counter);
                books.add(position, temp);
                break;
            }
        }
    }
}

For-loop is executed only once?

2 Answers2