Punit Jain

Ranch Hand

Posts: 1056

2

posted 5 years ago

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

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

Saloon Keeper

Posts: 7700

141

posted 5 years ago

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.

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

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

posted 5 years ago

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

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

Posts: 1056

2

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

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.