import
java.util.Comparator;
public class QuickSort {
public static void main(String
a[]) {
String[]
strs = { "one", "two", "three", "four", "five", "six",
"seven", "eight", "nine", "ten" };
quickSort(strs,
0, strs.length - 1);
for (String str :
strs) {
System.out.print(str);
System.out.print(" ");
}
}
/**
* This method will sort
the int type array in ascending order
* @param array
* @param start
* @param end
*/
public static void quickSort(int array[], int start, int end) {
int low = start;
int high = end;
if (low >= end)
{
return;
}
int mid =
array[(low + high) / 2];
while (low < high)
{
while (low < high
&& array[low] < mid) {
low++;
}
while (low < high
&& array[high] > mid) {
high--;
}
if (low < high)
{
int tmp =
array[low];
array[low]
= array[high];
array[high]
= tmp;
}
}
if (high < low)
{
int swap = high;
high
= low;
low
= swap;
}
quickSort(array,
start, low);
quickSort(array,
low == start ? low + 1 : low, end);
}
/**
* This method will sorts
the array of object in ascending order which implements Comparable.
* like String, Byte,
Short, Integer, Long, Float, Double, Character,
* Boolean, BigInteger,
BigDecimal
* @param <T>
* @param array
* @param start
* @param end
*/
public static <T extends
Comparable<T>> void quickSort(T[] array, int start, int end) {
int low = start;
int high = end;
if (low >= end)
{
return;
}
T
mid = array[(low + high) / 2];
while (low < high)
{
while (low < high
&& array[low].compareTo(mid) < 0) {
low++;
}
while (low < high
&& array[high].compareTo(mid) > 0) {
high--;
}
if (low < high)
{
T
tmp = array[low];
array[low]
= array[high];
array[high]
= tmp;
}
}
if (high < low)
{
int swap = high;
high
= low;
low
= swap;
}
quickSort(array,
start, low);
quickSort(array,
low == start ? low + 1 : low, end);
}
/**
* This method will sorts
the array of objects based on provided comparator in ascending order.
* @param <T>
* @param array
* @param start
* @param end
*/
public static <T> void quickSort(T[]
array, Comparator<T> comparator, int start, int end) {
int low = start;
int high = end;
if (low >= end)
{
return;
}
T
mid = array[(low + high) / 2];
while (low < high)
{
while (low < high
&& comparator.compare(array[low], mid) < 0) {
low++;
}
while (low < high
&& comparator.compare(array[high], mid) > 0) {
high--;
}
if (low < high)
{
T
tmp = array[low];
array[low]
= array[high];
array[high]
= tmp;
}
}
if (high < low)
{
int swap = high;
high
= low;
low
= swap;
}
quickSort(array,
comparator, start, low);
quickSort(array,
comparator, low == start ? low + 1 : low, end);
}
}
No comments:
Post a Comment