CODEWITHSUNDEEP
algorithmsorting
محمد قاسم
محمد قاسم

Reputation: 189

Sorting - How selection sort is efficient?

Recently I'm working on analysis of timing of basic sorting algorithms in C# Following this Book. On page 55 author mentions, in summary, that.

The Selection sort is the most efficient of the algorithms, followed by the Bubble sort and the Insertion sort

but in reality selection sort takes more time than insertion and bubble sort in best,normal & worst Cases. Even this online algorithm visualisation shows selection sort takes more time.

My Question is how selection sort is efficient as compared to Insertion and Bubble sort?

Upvotes: 2

Views: 1138

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727067

I think you generalized the author's claim too much.

When talking about relative efficiency, the author of the book compares the algorithms under very specific circumstances:

  • He compares the timing of his specific implementations,
  • He compares the timing on his specific hardware
  • He compares the timing on a randomized data set (as opposed to the animation page, which gives four choices)

By measuring the time under these specific circumstances the author arrives at the conclusion that his implementation of selection sort is fastest among the three implementations when 10,000 randomly-seeded elements are sorted on his specific hardware. That is the only claim that he can reasonably make. In particular, a claim that selection sort is somehow the most efficient among three is too general for the author's experiment.

The reason why author's experiment resulted in the ranking that he has shown is most likely the cache-friendliness of the algorithms.

Selection sort reads in a single direction most of the time, and most of its operations are reads. Insertion sort, on the other hand, does a lot of writing. Bubble sort also goes in the same direction most of the time, but it mixes writes with reads, and does more writing than selection sort does. In short, author's implementation of selection sort appears to be the most optimized of the three algorithms for author's hardware

Upvotes: 3

Geeky
Geeky

Reputation: 7496

I dont think selection sort is much efficient sorting algorithms of all but it is efficient than bubble sort but i doubt about insertion sort

because selection sort does inplace sorting,it removes the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far.

Insertion sort scans only as elements as needed to sort an element but selection sort has to scan whole list to sort any element.

See this example for selection sort

64 25 12 22 11

First it finds minimum element in this list ,it is 11

now swaps 11 and 64

11 25 12 22 64

next finds the minimum in 25 12 22 64, which is 12

so now the list is 11 12 25 22 64 this process continues

where as with insertion sort

64 25 12 22 11

it first checks 25 is less than 64

25 64 12 22 11

12 64 25 22 11

12 25 64 22 11

12 22 64 25 11

12 22 25 64 11

11 22 25 64 12

11 12 25 64 22

11 12 22 64 25

11 12 22 25 64

Time complexity of bubble,selection and insertion is O(n2)

Selection sort works well for smaller lists but i think they fail for large lists,For larger lists merge/quick sort are the best

Hope this helps

Upvotes: 0

Related Questions