Java Tutorial – Sorting and Searching Data

We also have some excellent Beginners Programming Java tutorials that use high quality narrated videos and practical working files to teach the fundamentals of programming in Java Beginners Java Tutorial CD

.

Java Tutorial – Sorting, Searching and Recursion

Once you start to use data structures in Java, you will inevitably encounter situations in which you need to sort or search through them. For the purposes of this beginners Java tutorial, we will use arrays to illustrate some basic sorting, searching and recursive algorithms.

An algorithm is a procedure, a series of steps that you define to solve a particular problem. In the examples below, our algorithms will be expressed in the Java code that we use in our programs.

Recursion

Some of the techniques we will be using rely on recursive processes, so let’s explore these first. A recursive method in your program is basically one that calls itself, i.e. within the method body, there will be a call to the method itself. Using recursive methods effectively can take a bit of practice, as your program can easily get caught in a loop, so you need to think the procedure in any such method through carefully.

To demonstrate a recursive function in action, let’s create a trivial example. Create a new Java project and enter the following in your main class, after the main method:

//recursive method
public static int doSomething(int someNumber)
{
		//check the value of the input parameter
	if(someNumber<=0)
		return someNumber;
	else
	{
			//decrement and call the method again
		someNumber--;
		System.out.println(someNumber);
		return(doSomething(someNumber));
	}
}

Now call the new method within your main method:

int result = doSomething(10);
System.out.println("done: " + result);

All the program does is count down from the passed int value to zero. Experiment by changing the value of the int parameter passed to the method and observe what effect it has on the output printed to the console. The method manages to avoid getting stuck in a loop (caused by calling itself repeatedly) by having the conditional ‘if’ statement.

This simple recursive method has much the same effect as a loop, but, as you’ll see, recursion can be particularly useful when you have a complex problem that is best solved in stages, each stage taking you a step closer to the solution by simplifying it. A necessary ingredient for recursive methods then is that you specify explicitly how the method should behave with the simplest input, and then with each iteration, you work towards this simplest case. In the example above, the simplest case is when the int parameter is less than or equal to zero.

Try not to worry if this seems an odd practice at first, once you start using sorting methods the recursive approach will become clearer.

Sorting

The main reason for keeping a collection of data in sorted order is that it is far easier to find items within the data and therefore maintain it effectively. Keeping the data in sorted order does, however, involve a certain amount of processing, particularly when adding or deleting items.

When we say, for example, that an array is in sorted order, we mean that the items within the array are arranged according to some understood ordering system. Sometimes this is intuitive, for example if the array contains numbers, sorted order will naturally comprise numbers stored according to ascending (or sometimes descending) numerical value. Similarly, if the array contains String values, sorted order will generally mean alphabetical order.

However, there are cases when sorted order will be less clear – imagine you have created your own class declaration for use within your program, and you wish to store objects of your class in the array. You will have to decide then what constitutes sorted order for these objects. In order to do this you have to think about comparing two objects of the same class. When you compare two objects of the class, it must be that case that either one is ‘greater’ than the other, or they are ‘equal’. This is how your objects will be ordered, and to provide this in your own classes they will need to implement the Comparable interface, which means that your objects provide a compareTo method. Within this method you will need to decide how to measure the objects of your class against one another, for example, you might decide to use the value of some variable in the class.

Note: be careful when using the ‘equals’ method on your objects also, as the default equals method inherited from the Class Object, actually tests the object references, i.e. it tests to see whether the two variable names are pointing to the same object. If you plan to use the equals method, you would be best to provide your own implementation of the method, overriding the default for this reason.

For the purposes of this Java tutorial, we will stick to simple types in order to illustrate the algorithms required.

Selection Sort

Selection sort works by continually finding the next smallest item in the collection and placing it at the front. Create a new program and enter the following code in your main method to create an array with some arbitrary data in it:

	//array with unsorted int data
int [] myData = {3, 1, 9, 5, 7};

Now we will use selection sort to arrange the items in the array in ascending numerical order. The selection sort technique is as follows:

• Within the section of data that is yet to be sorted (initially the whole structure), find the smallest item
• Place this item at the first position (of the unsorted section), swapping it with any element that’s already there
• The unsorted section now contains one less item (the item just deemed smallest and therefore moved)
• Continue placing the smallest unsorted item in first position until all of the data has been sorted

Enter the following code after declaring the array and compile your program, observing its output:

	//loop through the array
for(int pos=0; pos<myData.length-1; pos++)
{
		/* find and keep track of the smallest
		 * element's position
		 * -start at pos and look through the rest
		 * (pos is at the start of the unsorted section)
		 */
	int minIndex = pos;

		//loop through the unsorted section
	for(int next=pos+1; next<myData.length; next++)
	{
		if(myData[minIndex]>myData[next])
			minIndex=next;
	}

		//swap the item if necessary
	if(minIndex!=pos)
	{
			//keep track of the value currently at pos
		int temp = myData[pos];
			//copy the new smallest value into pos
		myData[pos] = myData[minIndex];
			//copy the swapped value into minIndex
		myData[minIndex] = temp;
	}

		//print the array for demonstration
	for(int p : myData)
	{	System.out.print(p);	}
	System.out.println();
}

When you look at the program output, try to work through which items are being swapped with one another at each stage – experiment by changing the int values (or their order) in the array.

Merge Sort

A more efficient approach to sorting the contents of an array is Merge Sort, which uses a recursive algorithm. This rests on the idea that merging two already sorted arrays is a simpler problem than sorting all of the data in one unsorted array. The algorithm therefore sorts an unsorted array by continually dividing it into two parts and sorting each part, merging the results into a final sorted array.

Add the following method to your program (after the main method):

/* mergeSort method sorts the data in a section of
	 * the array passed
	 * -parameters are the array containing the data to
	 *  be sorted, a temporary array for use with the
	 *  processing, and integers representing the start
	 *  and end positions of what data is to be sorted
	 *  within the array
	 */
public static void mergeSort(int[] dataArray, int[] tempArray,
							int start, int end)
{
		//array has been sorted
	if(start==end)
		return;
		//work towards sorted array by breaking the problem down
	else
	{
			//divide the data into two
		int center = (start+end)/2;
			//call the method on the first half
		mergeSort(dataArray, tempArray, start, center);
			//second half
		mergeSort(dataArray, tempArray, center+1, end);

			//merge the two halves into one sorted half
		int firstIndex = start;
		int secondIndex = center+1;
		int thirdIndex = start;

			//loop through both halves
		while(thirdIndex<=end)
		{
				/* work through both halves
				 * inserting smallest item into
				 * the temp array each time
				 */
			if(secondIndex>end ||
			(firstIndex<=center &&
			dataArray[firstIndex]<=dataArray[secondIndex]))
			{
				tempArray[thirdIndex]=dataArray[firstIndex];
				thirdIndex++;
				firstIndex++;
			}
			else
			{
				tempArray[thirdIndex]=dataArray[secondIndex];
				thirdIndex++;
				secondIndex++;
			}
		}
			//copy the temp contents into the main array
		for(int i=start; i<=end; i++)
			dataArray[i]=tempArray[i];
	}
}

Each time the method reaches the point of merging two halves, each half has already been sorted, since the mergeSort method has been first called on them, and on their subsections before they come to be merged, and so on. The method therefore solves the problem by repeatedly simplifying it and solving the simpler problems in turn. Now call the new method from your main method:

	//array to sort
int[] someData = {4, 3, 7, 6, 2, 8, 5, 9, 1};
	//extra helper array
int[] extraArray = new int[someData.length];
	//call the mergesort method on the whole array
mergeSort(someData, extraArray, 0, someData.length-1);

	//print the sorted array for testing
for(int pr : someData)
{ System.out.print(pr); }

Again, experiment by changing the values in the input array and observing the program output.

It can be difficult to get into the ‘recursive’ way of thinking and certainly requires practice, but once you do you will tend to find that you identify problems that could benefit from a recursive solution fairly quickly. It can help when writing a recursive method if you start from the simplest case, then take care of the steps that work towards it each time the method executes (rather than starting from the most complex input, which is the first one to be executed, and can therefore seem an intuitive starting point).

Searching

You will often face the task of finding a particular element in a data structure for one reason or another. If your array data is unsorted, the only way to do this is to look through each of the elements in turn. This is known as linear search – enter the following code in your main method:

//collection of arbitrary strings
String[] myStrings = {"potato", "carrot", "turnip",
		"onion", "leek", "courgette", "aubergine"};
	//find the index of 'leek'
int foundIndex=-1;
	//loop through the array
for(int veg=0; veg
	//binary search method
public static int binarySearch(String[] theData, String wanted)
{
		//-1 means item not found
	int foundIndex=-1;

		//keep track of both ends of searchable area
	int top = theData.length-1;
	int bottom = 0;

		//loop through, dividing searchable area each time
	while(bottom<=top)
	{
			//look at middle element
		int middle = (top+bottom)/2;

			//compare middle element to item searched for
		int comp = theData[middle].compareTo(wanted);

			//middle is item searched for
		if(comp==0)
			return middle;

			/* if middle element is greater,
			 * wanted element must be in lower half
			 * and vice-versa, so we reduce the
			 * searchable area accordingly
			 */

		else if(comp>0) //middle is greater
			top=middle-1;
		else //middle is lesser
			bottom=middle+1;

	}
		//finished searching
	return foundIndex;
}

Now call the method within your main method:

//array of sorted strings
String[] sortedStrings = {"aubergine", "carrot", "courgette",
		"leek", "onion", "potato", "turnip"};

	//call the method - returns -1 if item not found
int searchResult = binarySearch(sortedStrings, "potato");

System.out.println("found at index: "+searchResult);

Experiment with the code by searching for different elements in the array – you can also check how many iterations of the loop are required each time by including a System.out.print statement within the while loop in your binarySearch method. It is generally a good practice to include such ‘trace statements’ in your code, to check exactly what is happening at any stage in the program; it can be particularly helpful when debugging larger programs.

Although many of Java’s built-in datatypes provide sorting and searching methods, it can help with the efficiency of your own programs to think about the algorithms involved. Also, when you come to define your own data types, you may need to implement such methods yourself. There are numerous approaches to sorting and searching in Java, the examples above being only an introduction.

Advertisement