Why does this sorting algorithm work?

Question

I have the following algorithm to order an .txt file with 10 numbers

for (int i=0;i<array.length;i++)
{
    for(int j=i;j<array.length;j++)
    {
        if (array[i]<array[j])
        {
            temp=array[i];
            array[i]=array[j];
            array[j]=temp;
        }
    }
}

And it writes a new .txt file with all numbers in order. But with pen an paper it says it shouldn't work. It's the following:

7 10 4 3 5 8 1 3

The algorithm should do this:

10 7 4 3 5 8 1 3
10 8 4 3 5 7 1 3
10 8 5 3 4 7 1 3
10 8 5 4 3 7 1 3
10 8 5 4 7 3 1 3
10 8 5 4 7 3 3 1

Clearly, last line it's not in order, so why is the code doing it right? Or... where am I wrong when I doing it with pen and paper?

Algorithm is putting largest element at beginning starting for i = 0 till end. Pretty basic sorting algorithm with complexity of O(n2) — Shivam
– Shivam, Commented Jul 24, 2013 at 16:45

Erre Efe · Accepted Answer · 2013-07-24 16:42:20Z

5

Why it should not work? It's a pretty basic sorting algorithm (called selection sort). The problem with your pen and pencil is that you're forgetting about the outer for. Which continue sorting for every item. That's why its O(n^2) in complexity.

answered Jul 24, 2013 at 16:42

Erre Efe

15.6k10 gold badges47 silver badges80 bronze badges

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

Comments

Lochemage · Accepted Answer · 2013-07-24 16:59:40Z

I would re-check your third result:

10 8 5 3 4 7 1 3

You ended up with '5' as your third digit after it swapped the '4' out, but this is not finished. If you keep iterating the 'j' loop it will continue testing the rest of the digits. If we were to run that loop properly it would look more like this:

Starting with 10 8 4 3 5 7 1 3 where i points to the third digit '4':
if (4 < 4) false  // This is an unecessary step FYI, should start the loop with j=i+1
if (4 < 3) false
if (4 < 5) true, swap 4 with 5 = 10 8 5 3 4 7 1 3
  // This is where you seem to have stopped your loop and jumped directly to the next i,
  // However, there is no break and the j loop should continue on using the new third
  // digit '5'...
if (5 < 7) true, swap 5 with 7 = 10 8 7 3 4 5 1 3
if (7 < 1) false
if (7 < 3) false

You end up with the result 10 8 7 3 4 5 1 3 as your third iteration.

Fredrik · Accepted Answer · 2013-07-24 16:44:29Z

0

Why wouldn't it work? For each position i, the inner loop effectively moves the largest member of the rest of the list to that location (making it a selection sort).

I think your paper walkthrough went wrong on the third step; I get:

7 10 4 3 5 8 1 3 <- original list
^i
10 7 4 3 5 8 1 3
   ^i
10 8 4 3 5 7 1 3
     ^i
10 8 7 3 4 5 1 3
       ^i
10 8 7 5 3 4 1 3
...

answered Jul 24, 2013 at 16:44

Fredrik

9404 silver badges10 bronze badges

Collectives™ on Stack Overflow

Why does this sorting algorithm work?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related