Monday, July 2, 2012

Quick Sort in Java


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