CODEWITHSUNDEEP
algorithmsortingselection-sort
venkysmarty
venkysmarty

Reputation: 11431

Why are comparisons wasted in selection sort?

I am reading about selection sort in the Algorithms In A Nutshell book. The following appears in the book:

Selection sort is slowest of all the sorting algorithms. It repeatedly performs almost the same task without learning anything from one iteration to the next. Selecting the largest element, max, in A takes n-1 comparisons, and selecting the second largest element takes n-1 comparisons - not much progress! Many of these comparisons are wasted because if an element is smaller than second, it can't possibly be the largest element and therefore had no impact on the computation for the max.

What does the text in bold mean?

Can someone explain with simple example?

Upvotes: 0

Views: 150

Answers (2)

Aaron Digulla
Aaron Digulla

Reputation: 328594

The author of your book seems to like complicated, long sentences. Don't learn that from him; there are already enough people who know how to confuse their readers.

An attempt to make it more simple to understand:

Selecting the largest element from A takes n-1 comparisons when A has n elements. Unfortunately, the sort algorithm doesn't reuse any of this information.

When it starts the inner loop again to sort the remaining elements, it needs another n-2 comparisons (one element has been sorted to the right place with the last loop).

Since the sort only moves a single element per run of the inner loop, most of the comparisons are repeated over and over again without doing anything with the result - they are just a waste of time.

Wikipedia has a nice animation how selection sort works.

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55609

Consider 3,5,2,4,1.

The largest element is 5. The second largest element is 4.

3 is smaller than 4, thus it can't be larger than 5, thus checking whether it is is essentially a waste.

Upvotes: 0

Related Questions