Sorting Algorithm —- A Conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

This problem is about sorting: Suppose you have 100 numbers. They are 100 different cards and out of order. How can you sort them in ascending order?

Q: What is the unknown? What is your goal?
A: Find out a way to sort the numbers.
Q: What are the data?
A: 100 numbers written on cards that are not in order.
Q: Have you seen it before?
A: Well it is not hard to imagine. Just like you are sorting poker cards.
Q: OK Now tell me, how would you sort those cards?
A: Well, to start, I just pick a number and put it on the table. Then pick another one and compare this one with the former one. Based on the comparison, place it in the right position. And pick another one and compare this one with the former two and then place it in the right position. So this procedure just repeats: pick a new one, compare with the former ones and place it in the right position until there are no more new numbers to pick. I think this is a natural process to do.
Q: OK so you are doing a procedure repeatedly. What kind of component in programming is related to this?
A: Well loops. Eh and recursion?
Q: OK, so which one matches your need here?
A: I would say loop.
Q: So what should you do in the loop?
A: Like I said, pick a new number, compare with the former ones and place it in the right place.
Q: What is the ending condition?
A: The ending condition is that there is no more new number to pick.
Q: OK, you are comparing new number with former ones. what pattern do they have?
A: I’m not sure what you mean…
Q: OK, look at the unknown. What do we want to do with the data?
A: Sort the data and make sure they are in order.
Q: Now do the former numbers satisfy this condition when you exam them?
A: Eh, yeah sure.
Q: So they are…?
A: Sorted. in order.
Q: So every time you pick a new number, you are comparing it to data that are…?
A: Sorted. Yes I always compare the new number with data that are already sorted.
Q: Good. Now you mentioned that you need to place the new number correctly. Can you explain how to do it?
A: Well, we could start comparing the new number with the ones in the former sorted part one by one. If we found one N that is greater than the new number, then we should put it right before N.
Q: Well, what if the new number is larger than all numbers in the former sorted numbers?
A: In that case, we just put it at the end of the sorted numbers.
Q: Good. Do the former numbers have any other patterns?
A: Eh, every time I put a new number to the sorted part. So they are changing, if that counts.
Q: Sure. So it is changing and you need to use it every time. What should you do about it?
A: I guess I need to keep track of it.
Q: Good. Now you know you need a loop and what to do in the loop. Sounds like you have a plan. Be sure to check each step. Consider special cases. And when you are done, test it with some data to make sure you have the right algorithm.
=============================================================================
Q: Great now you have a solution for this problem. Is it possible to do it differently?
A: Eh, I don’t know.
Q: You mentioned recursion. Is it possible to solve this problem using recursion?
A: ….
Q: How does recursion usually works? What kind of problem does recursion apply to?
A: If you can solve a problem by dividing it into one or several sub-problems with smaller size that are similar or the same to the original problem, then you can consider recursion.
Q: Good, so can we apply it on our problem? What is the smaller problem here?
A: Well I can try. A smaller problem for us would be to sort a smaller collection of numbers. Say you have 50 numbers instead of 100.
Q: OK but your sub-problem must relate to the original problem. So these 50 numbers must be inside…
A: Oh right, these 50 numbers must be a subset of the original 100 numbers.
Q: Good. Now we only considered 50 numbers. What about the rest 50?
A: …
Q: You sorted 50 numbers. To get all 100 numbers sorted, what should you do about the rest?
A: Eh I guess we should sort them too. But I don’t know if we are heading to the right direction. At most we get two separately sorted collections. That is not the solution for the original problem.
Q: I’m glad you ask this question. Now the problem is whether we could get the sorted 100 numbers from two sorted subsets. Can you think about if this is possible?
A: …
Q: Can you think about an example of this situation?
A: OK, say we have 10 numbers: 3, 2, 1, 5, 6, 7, 9, 0, 8, 4. The final sorted array should be R(0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Assume we have two sorted subsets A (1,3,5,7,8) and B(0, 2, 4, 6, 9).  We are trying to get R from A and B. Hmm… interesting. We could just compare the head elements of both A and B, extract the smaller one from the collection it belongs to and put it in another collection C. W should repeat this process until one collection is empty (because of the extraction). Then if the other collection is not empty, just add the rest elements to C.
Q: Good call. Now for recursion, there are two cases. What are they?
A: Base case and recursive case.
Q: What is the base case?
A: The base case should be the case that the collection we are sorting only has one element and we can just return it.
Q: What about the recursive case?
A: eh we can divide the current collection in consideration into two subsets. Call the sort function on them and merge their results together and return it!
Q: Nice. Now you have a plan. Make sure you check each step and use some test cases on your algorithm.
Link to the Java Code on GitHub
Enhanced by Zemanta
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s