Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# problem in sortings

Punit Jain
Ranch Hand
Posts: 1012
2
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..

can anyone tell me how to learn them??

Thank you...

Stephan van Hulst
Bartender
Posts: 5432
52
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.

Anand Hariharan
Rancher
Posts: 272
• 1
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?

Punit Jain
Ranch Hand
Posts: 1012
2

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

Insertion Sort, isn't it??

Anand Hariharan
Rancher
Posts: 272
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.