File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes C / C++ and the fly likes problem in sortings Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Languages » C / C++
Bookmark "problem in sortings" Watch "problem in sortings" New topic
Author

problem in sortings

Punit Jain
Ranch Hand

Joined: Aug 20, 2011
Posts: 979
    
    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

Joined: Sep 20, 2010
Posts: 3577
    
  14

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

Joined: Aug 22, 2006
Posts: 257

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: 979
    
    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

Joined: Aug 22, 2006
Posts: 257

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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: problem in sortings
 
Similar Threads
GridBagLayout
Learning design pattern
Oracle SQL
Why will this KeyListener not work?
Good link for Log4J