[ Data Structures with Java ] Section 5.6 : Generic Search/Sorting Algorithms

Preface : 
In Chapter 4, we introduce an integer version of selectionSort(). A generic version is more functional. It can order arrays of different types. For each pass, the integer version of the method uses the operator < to identify the index of the smallest element in the unsorted tail of the list. The generic version specifies that the object type must implement the Comparable interface and uses compareTo() for the ordering relation. With minor adjustment to the code, we can implement a generic version of selectionSort(). Note the generic tag in the headers. You can find a listing of the method in Array class. 

Generic selection sort : 

- Array.java 代碼 (Partly)

view plaincopy to clipboardprint?

1. void selectionSort(T[] arr){  
2.     int smallIndex;  
3.     int pass, n=arr.length;  
4.     T temp;  
5.     for(pass=0; pass<(n-1); pass++) {  
6.         smallIndex = pass;  
7.         for(int j=(pass+1); j
8.             if(arr[smallIndex].compareTo(arr[j])>0) {  
9.                 smallIndex = j;  
10.             }  
11.         }  
12.         if(smallIndex!=pass) {  
13.             temp = arr[pass];  
14.             arr[pass] = arr[smallIndex];  
15.             arr[smallIndex] = temp;  
16.         }  
17.     }  
18. }  
19.   
20. public static void main(String args[]){  
21.     String[] strArr = {"red", "green", "blue"};  
22.     Integer[] intArr = {40, 70, 50, 30};  
23.     Arrays.selectionSort(strArr);  
24.     System.out.println("Sorted strings: "+  
25.             Arrays.toString(strArr));  
26.     Arrays.selectionSort(intArr);  
27.     System.out.println("Sorted integers: "+  
28.             Arrays.toString(intArr));  
29. }  

Output :
Sorted strings: [blue, green, red]
Sorted integers: [30, 40, 50, 70]

Generic Binary Search Method : 
The binary search may be used with any ordered array. Its implementation uses equality to detect a match and either less than (<) or greater than (>) to locate the sublist for the next iteration. A generic version of binSearch() requires that the object type implement the Comparable interface. You can find a listing of the method in the Arrays class. 

Generic binSearch() : 

- Arrays.java 代碼 (partly)

view plaincopy to clipboardprint?

1. int binSearch(T[] arr, int first, int last, T target) {  
2.     int mid;  
3.     while(first
4.         mid = (first+last)/2;  
5.         if(arr[mid].compareTo(target)==0) {  
6.             //System.out.println("Target="+target+",Object="+arr[mid]+", mid="+mid);  
7.             return mid;  
8.         } else if(arr[mid].compareTo(target)>0){  
9.             last = mid;  
10.             continue;  
11.         } else {  
12.             first = mid+1;  
13.             continue;  
14.         }  
15.     }  
16.     return -1;  
17. }  
18. public static void main(String args[]){  
19.     String[] strArr = {"red", "green", "blue", "orange", "tan"};  
20.     int index;  
21.     Arrays.selectionSort(strArr);  
22.     System.out.println("Sorted: "+Arrays.toString(strArr));  
23.     index = Arrays.binSearch(strArr, 0, strArr.length, "tan");  
24.     System.out.println("Find in "+index);  
25. }  

Output :
Sorted: [blue, green, orange, red, tan]
Find in 4

補充說明 : 
* JavaWorld@TW : Generics 簡介 [精華]