Tuesday, August 18, 2009

Quick Sort in Java

This class is a Quick Sort class that will sort a list of strings or Integers. You can use this sort class along with the sort interface that will return either a String, Integer or another object that you want sorted. If the ifInt is set to true, it will sort by an Integer.




/**
* Written by Greg Dias
*
* Purpose: This class is a Quicksort class that will sort
* a list by a String or a Day class.
* */
public class QuickSort
{
private List a;
/**
* This static variable if set to true, will sort
* the list by a Day class, if set to false, will sort
* the list by a String. The items in the list must
* implement the SortInterface. Sort by ifInt will take priority over sortDay.
* If sortDay is false and ifInt is false, then it will be sorted by string.
*/
public static boolean sortDay = false;

//Set to true if sort by integer
public static boolean ifInt=false;
/**
* Purpose: Pass in a List to be sorted that implements
* the SortInterface.
* Constructor
* @param anArray
*/
public QuickSort(List anArray)
{
a = anArray;
}

/**
* Purpose: This method must be called to sort the list.
*
*/
public void sort()
{
sort(0, a.size() - 1);
}

/**
* Purpose: Call this method if the user wants to set the high and low values.
* @param low
* @param high
*/
public void sort(int low, int high)
{
if(low >= high)
{
return;
} else
{
int p = partition(low, high);
sort(low, p);
sort(p + 1, high);
return;
}
}

private int partition(int low, int high)
{
Day day = null;
SortInterface sort5 = null;
String pivot = a.get(low).toString();
Day pivot2 = null;
int pivot3=0;
int sortValue=0;

if(sortDay)
{
sort5 = (SortInterface)a.get(low);
//day = sort5.getDay();
pivot2 = sort5.getDay(); //day;
}

if(ifInt)
{
sort5 = (SortInterface)a.get(low);
pivot3=sort5.getSortInteger();
}
int i = low - 1;
int j = high + 1;
do
{
if(i >= j)
break;
if(sortDay)
{
i++ ;
sort5 = (SortInterface)a.get(i);
for(day = sort5.getDay(); pivot2.compareTo(day) > 0&&(!(i>a.size()-1)); day = sort5.getDay())
{
i ++ ;
sort5 = (SortInterface)a.get(i);
}

j--;
sort5 = (SortInterface)a.get(j);
for(day = sort5.getDay(); pivot2.compareTo(day) < 0&&!(j==0); day = sort5.getDay())
{
j--;
sort5 = (SortInterface)a.get(j);
}

}
else if(ifInt)
{
i ++ ;
sort5 = (SortInterface)a.get(i);
for(sortValue = sort5.getSortInteger(); pivot3>sortValue&&(!(i>a.size()-1)); sortValue = sort5.getSortInteger())
{
i++ ;
sort5 = (SortInterface)a.get(i);
}

j--;
sort5 = (SortInterface)a.get(j);
for(sortValue = sort5.getSortInteger(); pivot3< sortValue&&!(j==0); sortValue = sort5.getSortInteger())
{
j--;
sort5 = (SortInterface)a.get(j);
}

}
else
{
for(i++ ; pivot.compareTo(a.get(i).toString()) > 0; i++ );
for(j--; pivot.compareTo(a.get(j).toString()) < 0; j--);
}
if(i < j)
{
SortInterface temp = (SortInterface)a.get(i);
a.set(i, a.get(j));
a.set(j, temp);
}

} while(true);
return j;
}


}

0 comments: