package cusack.algorithms.util;
import java.util.List;
public class SortUtils {
/**
* Sort the first n elements of the given array.
*
* @param theList The array to sort
* @param n How far into the array to sort.
*/
public static void insertionsort(int theList[], int n) {
for (int i = 1; i < n; i++) {
int T = theList[i];
int j = i - 1;
while (j >= 0 && theList[j] > T) {
theList[j + 1] = theList[j];
j--;
}
theList[j + 1] = T;
}
}
/**
* Sort the first n elements of the given array.
*
* @param theList The array to sort
* @param n How far into the array to sort.
*/
public static void insertionsort(Comparable theList[], int n) {
for (int i = 1; i < n; i++) {
Comparable T = theList[i];
int j = i - 1;
while (j >= 0 && theList[j].compareTo(T) > 0) {
theList[j + 1] = theList[j];
j--;
}
theList[j + 1] = T;
}
}
/**
* Sort the first n elements of the given list.
*
* @param theList The List to sort
* @param n How far into the list to sort.
*/
public static void insertionsort(List<Integer> theList, int n) {
for (int i = 1; i < n; i++) {
Integer T = theList.get(i);
int j = i - 1;
while (j >= 0 && theList.get(j).compareTo(T) > 0) {
theList.set(j + 1, theList.get(j));
j--;
}
theList.set(j + 1, T);
}
}
/**
* Sort elements from first to last in the array.
*
* @param theList The array to sort
* @param first The index (inclusive) of first element of the array to consider
* @param last The index (inclusive) of the last element of the array to consider
*/
public static void quickSort(int[] theList, int first, int last) {
if (first < last) {
int pivot = partition(theList, first, last);
quickSort(theList, first, pivot - 1);
quickSort(theList, pivot + 1, last);
}
}
/**
* The traditional partition algorithm for use with quickSort.
*
* @param theList The list to partition
* @param first The index (inclusive) of first element of the array to consider
* @param last The index (inclusive) of the last element of the array to consider
* @return The index of the element that has been put in the proper location.
*/
private static int partition(int theList[], int first, int last) {
int thePivot = theList[first];
int i = first + 1;
int j = last;
int empty = first;
while (true) {
while (i <= last && theList[i] < thePivot) {
i++;
}
while (j >= first && theList[j] > thePivot) {
j--;
}
if (i >= j)
break;
theList[empty] = theList[j];
theList[j] = theList[i];
empty = i;
i++;
j--;
}
if (j >= empty) {
theList[empty] = theList[j];
theList[j] = thePivot;
} else {
theList[empty] = thePivot;
j = empty;
}
return j;
}
/**
* Sort elements from first to last in the array.
*
* @param theList The array to sort
* @param first The index (inclusive) of first element of the array to consider
* @param last The index (inclusive) of the last element of the array to consider
*/
public static void quickSort(Comparable[] theList, int first, int last) {
if (first < last) {
int pivot = partition(theList, first, last);
quickSort(theList, first, pivot - 1);
quickSort(theList, pivot + 1, last);
}
}
/**
* The traditional partition algorithm for use with quickSort.
*
* @param theList The list to partition
* @param first The index (inclusive) of first element of the array to consider
* @param last The index (inclusive) of the last element of the array to consider
* @return The index of the element that has been put in the proper location.
*/
private static int partition(Comparable theList[], int first, int last) {
Comparable thePivot = theList[first];
int i = first + 1;
int j = last;
int empty = first;
while (true) {
while (i <= last && theList[i].compareTo(thePivot) < 0) {
i++;
}
while (j >= first && theList[j].compareTo(thePivot) > 0) {
j--;
}
if (i >= j)
break;
theList[empty] = theList[j];
theList[j] = theList[i];
empty = i;
i++;
j--;
}
if (j >= empty) {
theList[empty] = theList[j];
theList[j] = thePivot;
} else {
theList[empty] = thePivot;
j = empty;
}
return j;
}
/**
* Sort elements from first to last in the List. Note that this can be called with any List, including a LinkedList
* or an ArrayList.
*
* @param theList The array to sort
* @param first The index (inclusive) of first element of the array to consider
* @param last The index (inclusive) of the last element of the array to consider
*/
public static void quickSort(List<Integer> theList, int first, int last) {
if (first < last) {
int pivot = partition(theList, first, last);
quickSort(theList, first, pivot - 1);
quickSort(theList, pivot + 1, last);
}
}
/**
* The traditional partition algorithm for use with quickSort.
*
* @param theList The list to partition
* @param first The index (inclusive) of first element of the array to consider
* @param last The index (inclusive) of the last element of the array to consider
* @return The index of the element that has been put in the proper location.
*/
private static int partition(List<Integer> theList, int first, int last) {
Integer thePivot = theList.get(first);
int i = first + 1;
int j = last;
int empty = first;
while (true) {
while (i <= last && theList.get(i).compareTo(thePivot) < 0) {
i++;
}
while (j >= first && theList.get(j).compareTo(thePivot) > 0) {
j--;
}
if (i >= j)
break;
theList.set(empty, theList.get(j));
theList.set(j, theList.get(i));
empty = i;
i++;
j--;
}
if (j >= empty) {
theList.set(empty, theList.get(j));
theList.set(j, thePivot);
} else {
theList.set(empty, thePivot);
j = empty;
}
return j;
}
}