Selection Sort help

Hey all, I'm having problems with the selection sort algorithim!

What I'm having trouble with is finding the smallest variable in an array compared to all the others...I thought you could do an if statement going through every element with &&...But I realise that would be inpractical and quite lengthy for a large array.

My professor hasn't gone over the principles of the Selection Sort very well....Infact, all he said was the obvious of 'swapping the smallest variable with [0] and increment i (Which I understand that bit)....Because he skipped out on a detail, I'm guessing this is meant to be common sense...But I have been ill for the past 2 days, and any thinking with either the right or left side of my brain causes migraines....But that hasn't stopped me wanting to learn.

Any help/nice memory jog would be much appreciated. :)

- Twigstar

well complexit of selection sort is O(n^2) meaning: given n elements, it takes O(n^2) steps to sort them.
where that O is an approximation. like given n = 1.000 elements it takes approximately 1.000.000 (that is n^2 = 1000^2) steps to sort them.
(note that this is not the exact definition of O, "steps" in sorting algorithms are usually the number of comparissions required)

so youre right when you figure selection sort is sucky for large arrays

Ah right! Lol, it was my assumption that there was an important, complex piece of the algorithim I was missing out on....I was making it harder than it was (Which is seriously a habit I need to get out of).

Alright mate, thanks alot! :)

selection sort is unefficient, but it's only used for teaching purpouses. for real implementable ordering there are heapsort and quicksort which are a bit more complicated, but much more faster.

>but it's only used for teaching purpouses
Hardly. Quadratic sorts (including selection sort) are used for small sets of data where the performance of the "faster" algorithms degrades. Even more importantly, selection sort outperforms the "faster" algorithms when comparisons are cheap and copy operations are very expensive. Just because the time complexity of an algorithm says it's faster doesn't mean that it is in practice.

Defaulting to heapsort or quicksort without a second thought is silly. For example, you didn't consider mergesort, or how the data is stored, or how comparisons are performed, or how data is moved, and you automatically assumed a large data set. Most likely, you would have wasted a lot of time mucking about with a complicated algorithm when a simpler one would have performed adequately and you could have spent the extra time solving more interesting problems.

Man, all these algorithms I've got to look forward to! I will be buying a big ol introduction to algorithms book soon enough (When ye ol course demands it...They haven't stated which one is going to be needed...But I'm told it'll probably be "An Introduction to Algorithms"...It's retailed at $70 odd, but I'll wait till there's a cheap one floating about on Amazon. (That way, if they don't use that book - I'll not only have two steps ahead, but I wouldn't of cost me too much for extra do-it-yourself knowledge).

Thanks for the help and opinions guys! I know where to come when I hit an mental obstacle! (And if the Profs been drinking :rolleyes: )

- Twigstar