Thread: Insertion sort

  1. #1
    Wannabe Geek
    Join Date
    Aug 2004
    Posts
    19

    Insertion sort

    Hi,
    I'm programming in C(basic stuff mostly).
    I've got a selection sort and a bubble sort going.
    But what's an insertion sort and binary sort ? could you please explain these sorting techniques. also which is the most efficient?

    Thanx in advance.
    -cheers.

  2. #2
    Im a Capricorn vsriharsha's Avatar
    Join Date
    Feb 2002
    Posts
    192

    Thumbs up Available in FAQ

    Quote Originally Posted by Hypercase
    Hi,
    I'm programming in C(basic stuff mostly).
    I've got a selection sort and a bubble sort going.
    But what's an insertion sort and binary sort ? could you please explain these sorting techniques. also which is the most efficient?

    Thanx in advance.
    -cheers.
    Read the FAQ for Insertion Sort....

    Here is the Link


    -Harsha
    Help everyone you can

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >But what's an insertion sort and binary sort ?
    Insertion sort is basically how you would sort a hand while playing cards: Get a card, find where it needs to be, make room for it by shifting the larger cards over, then insert the card. Rinse and repeat until the entire hand is sorted.

    Binary sort I'm not familiar with. There's a binary tree sort, but it's not worth the effort. I imagine that you were thinking of binary searching, which is a completely different class of algorithm.

    >also which is the most efficient?
    Insertion sort is on the lower end of the totem pole, being a quadratic algorithm. Used alone it's only good for small sets of items, but because it is efficient with those small sets and almost sorted sets, insertion sort is used as a final step in more sophisticated sorting algorithms.
    My best code is written with the delete key.

  4. #4
    Registered User lobo's Avatar
    Join Date
    Oct 2001
    Posts
    71
    >There's a binary tree sort, but it's not worth the effort...
    Well i must disagree, it IS worth the effort if you sort 'bit' more then dozens of items. But there is possibly a cheaper alternative: QuickSort is quite effective on average (though it's quadratic in the worst case) and simple to understand and to code .

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >it IS worth the effort if you sort 'bit' more then dozens of items.
    No, it's not worth the effort simply because there are better and faster ways to sort data than creating a whole new data structure. If you need a binary search tree then okay, but if not, one of the nlogn algorithms will suit you nicely.
    My best code is written with the delete key.

  6. #6
    Registered User lobo's Avatar
    Join Date
    Oct 2001
    Posts
    71
    If we are chatting about the same method, then you do not need to create anything, just need good old array... that nlogn sentence is fully correct, but it's quite matter of discussion which method is yet 'simple' and which is not. To me, binary sorts are simple enough to use them if i need to sort sth. by myself . But i wanted to say that just because the complexity - my point is that there are quite simple nlogn or assymptotically nlogn aproaches - better than aforementioned insert sort.

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >If we are chatting about the same method
    Clearly we aren't. I'm talking about a binary search tree data structure, what are you talking about?
    My best code is written with the delete key.

  8. #8
    Registered User lobo's Avatar
    Join Date
    Oct 2001
    Posts
    71
    I replied to 'binary sort' as an approach, not to tree data structures.

  9. #9
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    Maybe binary sort is what we sometimes call radix sort or counting sort? A search for it found that the term differentiates between comparisions using the binary value of characters and those using the linguistical abstractions. For example, in spanish 'ch' is a distinct letter; sorts of spanish textual data would require a comparison function that is defined appropriately.

    Trees also can be implemented by two arrays if need be.

  10. #10
    Registered User lobo's Avatar
    Join Date
    Oct 2001
    Posts
    71
    Quite mess in terms, i guess... the sort i meant is commonly known as heap sort, binarity in it is hidden under binary heap it utilizes.
    Radix sort and counting sort belong to quite different class of sort algorithms - both in terms of usability and complexity.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 08-02-2008, 06:23 AM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Insertion Sort on Array of Structs
    By n0r3gr3tz in forum C Programming
    Replies: 3
    Last Post: 04-01-2008, 08:28 AM
  4. Insertion Sort Problem
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-08-2005, 12:30 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM