Sorting: Divide-and-Conquer, and Other Things

Sorting is a very common task in everyday life: articles of clothing in one’s drawer; collections of magazines; food stuff in the fridge; and lots of other things. Depending on the number of items there are, and how we use them, we have devised all different ways to sort: according to color, volume, date of acquisition or purchase, the like.

Similar to how lists have been adopted into computing, sorting has come to great use in computing. Today, sorting has become on of the most common computing tasks. Records in databases are usually sorted for better search efficiency. Items in binary trees are sorted accordingly so that operations can take advantage of this property.

Consequently, there has been a substantial amount of study spent on this subject and various algorithms has been devised. Some of these are obvious adaptations of natural methods of sorting utilized by humans in everyday life. While some are totally different, created for the purpose of sorting items which number in thousands or even millions. It should be noted, though, that there are still problems related to sorting that remain unsolved. New algorithms are constantly being developed and old ones improved.

Many useful sorting algorithms devised thus far take advantage of the divide-and-conquer approach to solving problems. Depending on the algorithm, a different way of division is used. For example, mergesort divides a collection in half. Quicksort divides a collection into big and small values while radix sort divides the problem by working on one digit of the key at a time.

There are lots of other useful sorting algorithms that have been created. Some of them work even together for better efficiency and performance. For instance, shellsort and quicksort both take advantage of the best case behavior of insertion sort to gain processing speed.

The most direct approach to comparing two sorting algorithms would be to program both and measure their running time. However, this can be misleading and might put a bias towards one of two depending on the input values especially when using input values favorable to this particular algorithm. Each algorithms has its own strength and one works better than the other depending on the data that needs processing. One is more efficient than the other depending on the application.

Any considerable discussion of any one of these sorting algorithms will require an article of their own. Which is why, the next few articles will each be dedicated to some of these sorting algorithms. We start with insertion sort. This takes Θ(n2) running time but it is easy to understand and implement; bubble sort and selection sort also take such a long run time. Nevertheless, they are occasionally the best tools for use depending on the situation.


From Clifford A. Shaffer’s A Practical Introduction to Data Structures and Algorithm Analysis Edition 3.1 (Java Version)

Advertisements

Three Steps: Beating the Problem

Writing computer programs can be as easy as 1-2-3 or as difficult as seeing the usefulness of understanding Einstein’s theory of relativity.

But any difficult problem always becomes easier when broken down into pieces. That way, you get to be able to see them as smaller problems and coding becomes easier from there.

General computer processes can usually be tackled with three steps: understand, specify and design. These three steps make higher programs become less.

Understand

First, it is important to understand the problem you are faced with. Your initial understanding need not be clear. However vague it may be doesn’t matter. The more important part is refining your understanding as you go along the entire coding process. Taking an inventory of the concepts in your problem helps a lot.

For example, if you are trying to build a chess program, you’ll want to begin with the notion of a “piece”, which could be the pawn, the rook, the knight, the bishop, the queen, or the king. Furthermore, note that each of these pieces have properties of “position” and “moves”.

Specify

Second, lay down how this problem can be converted to code.

In one part of the chess program, you can tackle player moves. This function can take a certain piece, its position on the board, and the new position to which it is being moved. The process of this program verifies whether the piece can be moved into the new position and outputs the result of the verification process – that is, moving the piece to the new position.

There are a few things to note when deciding a valid move:

  1. The type of the piece being moved. In chess, different pieces can only move in a certain manner. The rook can only move straight. The knight can only move in an L. The bishop can only move diagonally. There are limitations as to how a chess piece can move.
  2. The state of the new position. It can be so that the player is simply moving to a vacant square or the player can be trying to eliminate an opponent’s piece.
  3. The notion of promotion. Pawns that reach the other end can get promoted. Hence, it is important to note whether a certain piece have been moved to the opposite edge and whether promotion can happen.

These are some of the things you’ll want to consider when checking the validity of a move.

A similar specification process will work for other parts of the chess program.

You don’t have to think about it so hard in the initial phase. Things get improved as you go along your coding.

Design

Finally, you design working code.

Now that you know about the types of data you are dealing with and the functions associated with them, you can move on to writing your code.

Design of computer programs can take entire university level courses if the intention is to delve in.

Anyway, this step is where you initially write code. In the process, you get to be able to refine your understanding of the problem. Also, it might turn out that your specifications have been insufficient. So, you get back to that step and improve your specifications.

Basically, writing computer programs, and problem-solving in general, is a continuous process of refining and improving. Even Google’s search engine continues to be refined to this day despite the fact that, in all the sense of the word, it is already a complete program. Besides that, millions are already using it. Quite possibly even billions.

Therefore, this three-step process is more of an iterative process which you loop again and again while continuously improving your solution.