27

Selection Sort

Definition:

Selection sort is a type of sort algorithm that sort the unsorted arrays.

In worst, average and best case its time complexity is O(n^2) (n square). It is inefficient in large data sets. However, it has simple implementation and it does not require extra memory.

Its properties:

  • Not stable,
  • O(n^2) time complexity,
  • Not adaptive,
  • O (1) memory space,
  • In-place comparison sort,
  • O ( n) for swaps.

How does it work?

In selection sort, array is divided into 2 parts : sorted and unsorted list.

  1. Firstly, sorted list is empty, unsorted list has entire input.
  2. Find the smallest element in the unsorted list, and put it into sorted list.
  3. After all, array is sorted.

Example:

70  52  45  5   8  // initially
5  52  45  70  8 // sorted list= 5 
5  8  45  70 52 // sorted list= 5 8
5  8  45 70 52  // sorted list= 5 8 45 
5  8  45 52 70 // sorted list= 5 8 45 52 
5  8 45 52 70 // sorted list=  5 8 45 52 70

 

A figure below shows the selection sort:

Selection_sort_animation

Animated Selection Sort

Animation:

For better understanding, go to this animation page.

Pseudocode:

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/

Figure from:  http://en.wikipedia.org

 

For more algorithms, go to Algorithms Section.

omersezer

27 Comments

  1. Hello my loved one! I want to say that this article is awesome, great written and include approximately all important infos.
    I’d like to look extra posts like this .

  2. Thank you for sharing your info. I truly appreciate
    your efforts and I will be waiting for your further post thanks
    once again.

  3. Pretty nice post. I just stumbled upon your blog and wanted
    to say that I have really enjoyed surfing around your blog posts.
    In any case I’ll be subscribing to your feed and I hope you write again very soon!

  4. This is a topic that’s close to my heart… Thank you!

    Exactly where are your contact details though?

  5. I do not know whether it’s just me or if everyone else encountering
    issues with your website. It seems like some of the text in your
    content are running off the screen. Can someone else please provide feedback and let me know if this is
    happening to them too? This could be a problem with my browser because I’ve had
    this happen before. Appreciate it

  6. Howdy! Someone in my Myspace group shared this site with us
    so I came to take a look. I’m definitely enjoying the information. I’m bookmarking and will be tweeting this to my followers!
    Great blog and great design.

  7. Great post however , I was wondering if you could write a litte more on this subject?
    I’d be very thankful if you could elaborate a little
    bit further. Thank you!

  8. My brother suggested I might like this blog.

    He was entirely right. This post truly made my day.
    You can not imagine simply how much time I had spent for this info!
    Thanks!

  9. I’ve been surfing online more than 2 hours today, yet I never found any interesting article like
    yours. It’s pretty worth enough for me. In my view, if all website
    owners and bloggers made good content as you did,
    the internet will be a lot more useful than ever before.

  10. Oh my goodness! Incredible article dude! Thank you, However I am going through issues
    with your RSS. I don’t know the reason why
    I can’t subscribe to it. Is there anybody else having similar RSS issues?
    Anyone who knows the answer can you kindly respond? Thanx!!

  11. Excellent blog you’ve got here.. It’s difficult to find excellent
    writing like yours nowadays. I really appreciate individuals like you!

    Take care!!

  12. It’s amazing to go to see this web page and reading the
    views of all colleagues regarding this article, while I am also zealous of getting experience.

  13. Having read this I believed it was rather enlightening.
    I appreciate you taking the time and effort to put this content
    together. I once again find myself personally spending a lot of time both reading and
    leaving comments. But so what, it was still worthwhile!

  14. There’s certainly a lot to learn about this topic.
    I like all the points you made.

  15. Hi there, just wanted to mention, I enjoyed this blog post.

    It was practical. Keep on posting!

  16. This is my first time go to see at here and i am actually impressed to read all at single place.

  17. Wow, awesome blog layout! How long have you been blogging
    for? you make blogging look easy. The overall look
    of your site is great, let alone the content!

  18. Oh my goodness! Incredible article dude! Thanks, However I am encountering troubles
    with your RSS. I don’t understand why I am unable
    to subscribe to it. Is there anybody else getting similar
    RSS problems? Anyone who knows the solution will you
    kindly respond? Thanks!!

  19. Hi great website! Does running a blog like this take a massive amount work?
    I have no understanding of computer programming however I
    was hoping to start my own blog soon. Anyhow, should
    you have any suggestions or techniques for new blog owners please share.
    I know this is off subject nevertheless I simply needed to ask.
    Thanks a lot!

  20. Thanks for any other magnificent post. The place else may just anyone get
    that type of information in such a perfect means of writing?
    I have a presentation subsequent week, and I am
    on the search for such information.

  21. Write more, thats all I have to say. Literally, it seems
    as though you relied on the video to make your point.

    You clearly know what youre talking about, why throw away your intelligence on just posting
    videos to your weblog when you could be giving us something enlightening
    to read?

  22. I blog often and I really thank you for your information. The article has truly peaked my interest.
    I am going to take a note of your site and keep checking for new information about once
    per week. I opted in for your Feed as well.

  23. Hi there, I found your web site by way of Google while looking for a comparable topic, your website got here up, it appears good.

    I’ve bookmarked it in my google bookmarks.
    Hello there, simply became alert to your blog through Google, and located that it’s really
    informative. I’m going to watch out for brussels. I’ll appreciate if you proceed this in future.
    Many other people will probably be benefited out of your writing.
    Cheers!

  24. Hello my family member! I wiish to say that this
    post is awesome, great written and include almost all significant infos.
    I’d like to see more posts like this .

  25. This is very interesting, You are a very skilled blogger.
    I have joined your feed and look forward to seeking more of your fantastic
    post. Also, I’ve shared your site in my social networks!

Leave a Reply

Your email address will not be published. Required fields are marked *