Getting started with sorting

The sorting problem is one of the oldest programming tasks that an engineer deals with. We have a set of records and we know that we want to find a specific one sometime later, and we want to find that one fast. To find it, we sort the records in a specific order that helps us find the record we want quickly.

As an example, we have the names of students with their marks on some cards. When students come to the office asking for their results, we look through all of the cards one after the other to find the name of the enquiring student. However, it is better if we sort the cards by the names of the students alphabetically. When a student makes an enquiry, we can search the mark attached to the name much faster.

We can look at the middle card; if it shows the name of the student, then we are happy to have found the name and the mark. If the card precedes the name of the student alphabetically, then we will continue searching in the second half; otherwise, we will check the first half.

Following that approach, we can find the name of the student in a few steps. The number of steps can not be more than the number as many times the pack of cards can be halved. If we have two cards, then it is two steps at most. If it is four, then we will need three steps at most. If there are eight cards, then we may need four steps, but not more. If there are 1,000 cards, then we may need at most 11 steps, while the original, non-sorted set will need 1,000 steps, worst case. That is, approximately, it speeds up the search 100 times, so this is worth sorting the cards, unless the sorting itself takes too much time. The algorithm finding an element in the already sorted set we just described is called binary search (https://en.wikipedia.org/wiki/Binary_search_algorithm).

In many cases, it is worth sorting the dataset, and there are many sorting algorithms to do that. There are simpler and more complex algorithms, and, as in many cases, more complex algorithms are the ones that run faster.

As we are focusing on the Java programming part and not the algorithm forging, in this chapter, we will develop a Java code that implements a simple and not-that-fast algorithm.