Tuesday, August 14, 2012

Java Generic QuickSort

Reference : http://en.wikipedia.org/wiki/Quick_sort
package sorting; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import types.Employee; public class QuickSort { private Object[] _dataToBeSorted = null; //comparator to compare any type of element private Comparator<Object> _comparatorForData = null; public QuickSort(Object[] data, Comparator<Object> comparator){ _dataToBeSorted = data; _comparatorForData = comparator; } public Object[] sort(){ return sort(_dataToBeSorted); } private Object[] sort(Object[] dataToBeSorted){ //if the dataToBeSorted is empty return as it is. if(dataToBeSorted == null || dataToBeSorted.length < 1){ return dataToBeSorted; } //find pivot int pivotIndex = dataToBeSorted.length/2; List<Object> lessThan = new ArrayList<Object>(); List<Object> greaterThan = new ArrayList<Object>(); //separate elements less than pivot and greater than pivot for(int i=0; i < dataToBeSorted.length; i++){ if(i == pivotIndex){ continue; }else if(_comparatorForData.compare(dataToBeSorted[i], dataToBeSorted[pivotIndex]) >= 0){ greaterThan.add(dataToBeSorted[i]); }else if(_comparatorForData.compare(dataToBeSorted[i], dataToBeSorted[pivotIndex]) < 0){ lessThan.add(dataToBeSorted[i]); } } List<Object> sortedData = new ArrayList<Object>(); //join collected less than elements on the left of the pivot after sorting them (recursive). for(Object objToAdd:this.sort(lessThan.toArray())) sortedData.add(objToAdd); sortedData.add(dataToBeSorted[pivotIndex]); //join collected greater than elements on the right of the pivot after sort them (recursive). for(Object objToAdd:this.sort(greaterThan.toArray())) sortedData.add(objToAdd); return sortedData.toArray(); } public static void main(String[] args) { /*//Integer Object[] data = {2,3,1,5,4}; Comparator<Object> comparator = new Comparator<Object>() { @Override public int compare(Object m1, Object m2) { Integer o1 = (Integer) m1; Integer o2 = (Integer) m2; if(o1 == o2) return 0; else if(o1 > o2) return 1; return -1; } };*/ /*//String Object[] data = {"xyz","abc","mno"}; Comparator<Object> comparator = new Comparator<Object>() { @Override public int compare(Object m1, Object m2) { String o1 = (String) m1; String o2 = (String) m2; if(o1.equals(o2)) return 0; else if(o1.compareTo(o2) > 0) return 1; return -1; } };*/ //Employee Employee e1 = new Employee("c1", "xyz", 26); Employee e2 = new Employee("c2", "abc", 25); Employee e3 = new Employee("c3", "mno", 27); Object[] data ={e1, e2, e3}; /*Comparator<Object> comparator = new Comparator<Object>() { @Override public int compare(Object m1, Object m2) { Employee o1 = (Employee) m1; Employee o2 = (Employee) m2; if(o1.name.equals(o2.name)) return 0; else if(o1.name.compareTo(o2.name) > 0) return 1; return -1; } };*/ Comparator<Object> comparator = new Comparator<Object>() { @Override public int compare(Object m1, Object m2) { Employee o1 = (Employee) m1; Employee o2 = (Employee) m2; if(o1.age == o2.age) return 0; else if(o1.age > o2.age) return 1; return -1; } }; QuickSort quickSort = new QuickSort(data, comparator); for(Object a : quickSort.sort()){ System.out.println(a.toString()); } } }

No comments:

Post a Comment