Thread: Selection Sort help

  1. #1
    Code Monkey
    Join Date
    Jun 2005
    Posts
    25

    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

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    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
    signature under construction

  3. #3
    Code Monkey
    Join Date
    Jun 2005
    Posts
    25
    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!

  4. #4
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    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.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  6. #6
    Code Monkey
    Join Date
    Jun 2005
    Posts
    25
    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 )

    - Twigstar

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Selection Sort Problem?
    By dcwang3 in forum C Programming
    Replies: 31
    Last Post: 11-07-2008, 01:25 PM
  2. Insertion and selection sort
    By Dashing Boy in forum C Programming
    Replies: 4
    Last Post: 08-29-2006, 04:42 PM
  3. Selection Sort problem #2
    By Twigstar in forum C++ Programming
    Replies: 7
    Last Post: 07-11-2005, 07:27 PM
  4. Selection Sort
    By Bleueyes515 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2002, 08:33 PM
  5. selection sort records of chars
    By hew in forum C++ Programming
    Replies: 8
    Last Post: 04-23-2002, 03:49 PM