Sorting/Searching practice

APCompSci.java

abstract class Structure {
	public final int ASCENDING=1;
	public final int DESCENDING=-1;
	public final int NONE=0;
	
	protected int[] storage;
	protected boolean sorted;
	protected int order;
	
	/* Determine the ordering state of storage */
	protected int detOrder() {
		/* Let's see if we're ordered or not */
		int prev=storage[0];
		sorted=true;
		int order=ASCENDING;
		// Check ascending first
		for(int i=1; i<storage.length; i++) {
			if(!(prev<=storage[i])) {
				sorted=false;
				order=DESCENDING;
				break;
			}
			prev=storage[i];
		}
		
		// It might be descending
		if(!sorted) {
			prev=storage[0];
			for(int i=1; i<storage.length; i++) {
				if(!(prev>=storage[i])) {
					order=NONE;
					break;
				}
				prev=storage[i];
			}
			
			if(order!=NONE) sorted=true;
		}
		
		return order;
	}
	
	public int[] getStorage() {
		return storage;
	}
	
	public String getOrder() {
		order = detOrder();
		
		if(order==ASCENDING) return "Ascending";
		if(order==DESCENDING) return "Descending";
		
		return "No";
	}
	
	// Return a string representation of storage
	public String toString() {
		StringBuilder storage=new StringBuilder();
		
		for(int i=0; i<this.storage.length; i++) {
			storage.append(Integer.toString(this.storage[i]) + " ");
		}
		
		return storage.toString();
	}
	
	
	public Structure(int[] initial) { storage=initial; }
}

class Sorter extends Structure {
	/* Swap the item at index a with the item at index b */
	private void swap(int a, int b) {
		int temp=storage[b];
		storage[b]=storage[a];
		storage[a]=temp;
	}
	
	public Sorter(int[] initial) {
		super(initial);
		
		order=detOrder();
	}
	
	/* order - what order should it be sorted in? */
	public void selectionSort(int order) {
		if (order!=NONE) {
			
			for(int n=0; n<storage.length; n++) {
				int token=storage[n];
				int tokenIndex=n;
				for(int i=n+1; i<storage.length; i++) {
					if(storage[i]*order<token*order) {
						tokenIndex=i;
						token=storage[i];
					}
				}
				swap(n, tokenIndex);
			}
		}
		else
			System.out.println("Specify a valid order.");
	}
	
	public void insertionSort(int order) {
		
	}
	
	public void mergeSort(int order) {
		
	}
}

class Searcher extends Structure {
	
	public Searcher(int[] initial) {
		super(initial);
		
		order=detOrder();
	}
	
	// Returns the index of 'key'
	public int sequentialSearch(int key) {
		for (int i=0; i<storage.length; i++) {
			if(storage[i]==key)
				return i; // Eureka!
		}
		
		return -1; // Key is not in list
	}
	
	public int binarySearch(int key) {
		if (order!=NONE) return binarySearch(key, 0, storage.length);
		
		System.out.println("List isn't sorted, cannot use binary search");
		return -1;
	}
	
	private int binarySearch(int key, int low, int high) {
		if (low<=high) { // There are still elements in the array
			int mid=(low+high)/2;
			if(key==storage[mid]) return mid;
			else if (key*order<storage[mid]*order) // Key is in left half
				return binarySearch(key, low, mid-1);
			else // Key is in right half
				return binarySearch(key, mid+1, high);
		}
		
		return -1; // Not found
	}
}

public class APCompSci {

	public static void main(String[] args) {
		int[] arr = new int[20];
		for(int i=0; i<arr.length; i++)
			arr[i]=(int)(Math.random() * arr.length);
		
		Sorter list=new Sorter(arr);

		System.out.println("Before sort: "+list.getOrder()+" order.");
		System.out.println(list.toString());
		
		list.selectionSort(list.ASCENDING);
		
		System.out.println("After sort: "+list.getOrder()+" order.");
		System.out.println(list.toString());
		
		Searcher search=new Searcher(list.getStorage());
		int key=(int)(Math.random() * arr.length);
		
		int index=search.sequentialSearch(key);
		
		System.out.println("[Sequential] Location of "+Integer.toString(key)+" in list: "+Integer.toString(index));
		
		index=search.binarySearch(key);
		
		System.out.println("[Binary] Location of "+Integer.toString(key)+" in list: "+Integer.toString(index));
	}

}