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

A selection sort could indeed be described as a greedy algorithm, in the sense that it:

• tries to choose an output (a permutation of its inputs) that optimizes a certain measure ("sortedness", which could be measured in various ways, e.g. by number of inversions), and
• does so by breaking the task into smaller subproblems (for selection sort, finding the k-th element in the output permutation) and picking the locally optimal solution to each subproblem.

As it happens, the same description could be applied to most other sorting algorithms, as well — the only real difference is the choice of subproblems. For example:

• insertion sort locally optimizes the sortedness of the permutation of k first input elements;
• bubble sort optimizes the sortedness of adjacent pairs of elements; it needs to iterate over the list several times to reach a global optimum, but this still falls within the broad definition of a greedy algorithm;
• merge sort optimizes the sortedness of exponentially growing subsequences of the input sequence;
• quicksort recursively divides its input into subsequences on either side of an arbitrarily chosen pivot, optimizing the division to maximize sortedness at each stage.

Indeed, off the top of my head, I can't think of any practical sorting algorithm that wouldn't be greedy in this sense. (Bogosort isn't, but can hardly be called practical.) Furthermore, formulating these sorting algorithms as greedy optimization problems like this rather obscures the details that actually matter in practice when comparing sorting algorithms.

Thus, I'd say that characterizing selection sort, or any other sorting algorithm, as greedy is technically valid but practically useless, since such classification provides no real useful information.

Answer 2

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]