Why selection sort is not greedy

Question

I have found out that selection sort uses Brute Force strategy. However, I think that it uses Greedy strategy.

Why do I think that it uses Greedy: it goes from 0 to n-1 at it outer loop and from i+1 to n-1. This is really naive. It selects the minimum element in one every iteration - it chooses best locally. Everything like in Greedy but it is not.

Can you please explain me why it is not how I think? Information about this issue I have not found in the Internet.

Answer 1

Let A be a list of intgers such that: A = [5, 4, 3, 6, 1, 2, 7 ]

A greedy algorithm will look for the most promising direction, therefore :

1. we will compare: 5 to 4, see that 4 is indeed smaller than 5, set 4 as our minimum
2. compare 4 to 3 , set 3 as our minimum
3. Now we compare 3 to 6 and here is the tricky part: while in a normal selection sort(brute force) we will keep considering the remaining numbers, in a greedy approach we will take 3 as our minimum and will not consider the remaining numbers, hence "Best locally".

so a sorted list using this approach will result in a list sorted as such: [3, 4, 5, 1, 2, 7]