We have already seen some examples of sorting algorithms in an earlier lecture. Since sorting is such an important topic in computer science, there are actually many sortingalgorithms available.
The best sorting algorithm we have seen so far is merge sort. Merge sort is very fast: it can sort a list of N items in time proportional to N log N. Merge sort is however not very space efficient, because it needs to make copies of the data it is working with.
Quicksort is an algorithm that is as fast as Merg sort, if not faster. Quicksort is also an example of an in place sorting algorithm, which does all of its work by moving numbers around within the original array.
The Quicksort algorithm, like the Merge sort algorithm, uses a divide and conquer strategy. Quicksort starts with a partitioning step that partially reorganizes the original list into small numbers and large numbers. After the initial partition step Quicksort then goes to work further sorting the two smaller lists created by the partition step.
Here is the Java code for a partition method which does the initial partial sorting. The partition step operates on a portion of an array from index start up through index end. Partition selects one of the numbers from that range as the pivot value, and then reorganizes the numbers in the given range into numbers that are less than or equal to the pivot, the pivot itself, and then numbers that are greater than the pivot. Partition does not aim to fully sort the numbers in the two sublists. After partition finishes its work it returns the index where the pivot value ended up.
private static int partition(int[] list,int start,int end) {
// Use the element at end as the pivot
int pivot = list[end];
// Main loop
int i = start-1;
for(int j = start;j<end;j++) {
// Move any small numbers you find to the left side of the list
if(list[j] <= pivot) {
i++;
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
// Move the pivot to the middle
list[end] = list[i+1];
list[i+1] = pivot;
// Return the location of the pivot
return i+1;
}
Here now is the code for the Quicksort method itself.
public static final int THRESHOLD = 40;
private static void quicksort(int[] list,int start,int end) {
if(end - start < THRESHOLD)
selectionSort(list,start,end);
else {
int mid = partition(list,start,end);
quicksort(list,start,mid-1);
quicksort(list,mid+1,end);
}
}
Like Merge sort, QuickSort uses a recursive structure where the method calls its self after dividing the problem into smaller pieces. The partition step will break the original range from start to end into two smaller ranges, [start,mid-1] and [mid+1,end]. To finish sorting those smaller ranges, QuickSort simply calls itself with the two smaller ranges.
One final feature that QuickSort uses is similar to the strategy that Merge sort uses: once you ask QuickSort to work with a sufficiently short range, it will pass of the remaining sorting work to a simpler algorithm like selection sort. Although selection sort is inefficient for sorting longer lists, it sorts short lists quickly enough to be useful here.
Sorting lists is an essential first step for solving many problems. A common problem in computer science is the searching problem. Given a list of data items and particular item to search for, we would like to know whether or not the given item appears in the list.
The simplest search strategy is linear search, which involves a simple loop to do the search:
public static boolean search(int A[],int x) {
for(int n = 0;n < A.length;n++)
if(A[n] == x]
return true;
return false;
}
This method is effective, but is not the most efficient way to do a search. If the list we are searching in is sorted, we can use a much more efficient algorithm called binary search.
public static int find(int list[],int x) {
int start = 0;
int end = list.length - 1;
while(start < end) {
int mid = (start+end)/2;
if(list[mid] == x) {
while(mid > 0 && list[mid-1] == x)
mid--;
return mid;
}
if(list[mid] < x)
start = mid + 1;
else
end = mid - 1;
}
if(list[start] < x)
return start+1;
return start;
}
This algorithm also uses a divide and conquer strategy. To search for an item we go to the middle of the list and compare the item we see there with the item we are searching for. If the item in the middle is smaller than the item we are searching for, we know right away that we can ignore the entire half of the list the comes before the middle. We then repeat the search process with the numbers in the second half of the list. By repeatedly subdividing the range we are searching in we can very quickly narrow down the part of the list that may contain the number we are searching for.
The sorting code I have been showing so far in this course was all designed to sort lists of ints. In many applications in Java we may instead have to sort lists of objects. For example, the produce tracker example I showed in the last lecture printed a report that shows how much of each item was in stock at the end of the day. If we wanted to print those items in alphabetical order we would need some way to sort our list of Item objects.
The standard way to make objects sortable in Java is to equip them with a special method called the compareTo method. This method can be applied to an object, and takes a single parameter which is another object that you want to compare this object to. compareTo returns an int: it returns 0 if the two objects are the same, -1 if the object you apply the method to is less than the object in the parameter, and 1 if the object you apply the method to is greater than the object in the parameter.
Here is the compareTo method for the Item class that compares two items using their names:
public int compareTo(Item other) {
return name.compareTo(other.name);
}
This code takes advantage of the fact that many classes in Java already have compareTo methods. The String class has a compareTo method that uses alphabetical order to compare Strings, so all we have to do here is to call that method on the names of the two Items we are comparing.
One final thing you need to do to make this all work is to slightly modify the structure of the class in which you want to place a compareTo method. To notify other classes that your class has a compareTo method, you declare that your class implements the Comparable interface:
public class Item implements Comparable<Item>
Once you have added this declaration and the compareTo method to one of your classes, you can use that class in combination with things like sorting algorithms that are available in Java for sorting lists of objects.
We have already seen that the ArrayList is a common way to store lists of objects in Java. To sort a list of objects stored in an ArrayList, we can use the static sort() method in the java.util.Collections class to sort the ArrayList.
For example, here is modified code for the Inventory class's printReport() method that uses Collections.sort() to sort the stock list before printing the report.
public void printReport() {
Collections.sort(stock);
for (int n = 0; n < stock.size(); n++) {
Item i = stock.get(n);
System.out.println(i);
}
}