can anone tell me which is the best way to learn sortings techniques (ie. bubble, quick, merge etc.).
the basic difference between each sorting program is in their loops when we write code in c or any other language.
i every time gets confused, in all the sortings, and messed up everyting while i appear for my college exams..

You should find a description of how the algorithm works, then implement it in the language of your choice. Test your algorithm on a bunch of unsorted lists, and see if it works correctly.

The best way to understand the workings of something is to build it.

My teacher gave this exercise where he gave a sequence of random numbers and asked us to show us the state of this sequence after every iteration of a sort that he just taught.

PLUS: (1) Language independent. (2) Gives you an idea of how poor bubble sort is versus say heap sort. (3) Gets you to understand O(1) storage versus O(n) storage (*).

MINUS: You don't get to pull your hair with the nuts and bolts of managing indices, debugging something that goes wrong when you get incorrect output or infinite loop or ...

Note that I am not being facetious: What I presented as a MINUS is indeed a -ve point of this approach. There is a learning process and a joy in the approach recommended by Stephen that you do not get in the approach my teacher followed. For example, while I can conceptually explain how heap sort works, chances are, I won't get it correct the first time if I am required to implement it in a zero-based container.

(*): Pop-quiz -- Which sorting algorithm that has the best, average and worst-case complexity of O(n lg n) requires a O(n) storage?

"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery

Punit Jain
Ranch Hand

Joined: Aug 20, 2011
Posts: 1012

2

posted

0

(*): Pop-quiz -- Which sorting algorithm that has the best, average and worst-case complexity of O(n lg n) requires a O(n) storage?

No, insertion sort is typically done in O(1) space (it entails not just key comparisons but several swaps as well). It is Merge Sort that requires O(n) space. One can do an in-place merge, but then the complexity of the computation goes up.