1. ## 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?

-cheers.

2. ## Available in FAQ

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?

-cheers.
Read the FAQ for Insertion Sort....

-Harsha

3. >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.

4. >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. >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.

6. 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. >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?

8. I replied to 'binary sort' as an approach, not to tree data structures.

9. 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. 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.