Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

problem in sortings

 
Punit Jain
Ranch Hand
Posts: 1012
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 5432
52
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
C++ Debian VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

(*): 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
C++ Debian VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic