CODEWITHSUNDEEP
javanested-loops
Vivi Xu
Vivi Xu

Reputation: 131

Get confused with nested loops

I know the rationale behind nested loops, but this one just make me confused about the reason it wants to reveal:

public static LinkedList LinkedSort(LinkedList list)
{
   for(int k = 1; k < list.size(); k++)
    for(int i = 0; i < list.size() - k; i++)
    {
        if(((Birth)list.get(i)).compareTo(((Birth)list.get(i + 1)))>0)
        {
            Birth birth = (Birth)list.get(i);
            list.set( i,  (Birth)list.get( i + 1));
            list.set(i + 1, birth);
    }
}
return list;
}

Why if i is bigger then i + 1, then swap i and i + 1? I know for this coding, i + 1 equals to k, but then from my view, it is impossible for i greater then k, am i right? And what the run result will be looking like? I'm quite confused what this coding wants to tell me， hope you guys can help me clarify my doubts, thank you.

Upvotes: 2

Views: 287

Answers (2)

Thomas Stets
Thomas Stets

Reputation: 3035

This method implements a bubble sort. It reorders the elements in the list in ascending order. The exact data to be ordered by is not revealed in this code, the actual comparison is done in Birth#compare.

Lets have a look at the inner loop first. It does the actual sorting. The inner loop iterates over the list, and compares the element at position 0 to the element at position 1, then the element at position 1 to the element at position 2 etc. Each time, if the lower element is larger than the higher one, they are swapped.

After the first full run of the inner loop the largest value in the list now sits at the end of the list, since it was always larger than the the value it was compared to, and was always swapped. (try it with some numbers on paper to see what happens)

The inner loop now has to run again. It can ignore the last element, since we already know it contains the largest value. After the second run the second largest value is sitting the the second-to-last position.

This has to be repeated until the whole list is sorted.

This is what the outer loop is doing. It runs the inner loop for the exact number of times to make sure the list is sorted. It also gives the inner loop the last position it has to compare to ignore the part already sorted. This is just an optimization, the inner loop could just ignore k like this:

for(int i = 0; i < list.size() - 1; i++)

This would give the same result, but would take longer since the inner loop would needlessly compare the already sorted values at the end of the list every time.

Upvotes: 3

Tomas
Tomas

Reputation: 71

Example: you have a list of numbers which you want to sort ascendingly:

4 2 3 1

The first iteration do these swap operations: swap(4, 2), swap(4, 3), swap(4, 1). The intermediate result after the 1st iteration is 2 3 1 4. In other words, we were able to determine which number is the greatest one and we don't need to iterate over the last item of the intermediate result.

In the second iteration, we determine the 2nd greatest number with operations: swap(3, 1). The intermediate result looks then 2 1 3 4.

And the end of the 3rd iteration, we have a sorted list.

Upvotes: 2

Related Questions