Thursday, December 24, 2015

Quick Sort 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
/**
 * Simple Quick sort
 * 
 * Time Complexity: 
 *    Average - O(nLogn)
 *    Worst case - O(n^2)
 * 
 * Note:
 *   - Is in-place algorithm
 *   - 39% more compare than merge sort
 *   - Faster than merge sort in practice because of less data movement 
 * 
 * @author ramesh
 *
 */
public class Quicksort {
 private static final int ARRAY_DEFAULT_SIZE = 20;

 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);

  List<String> list = new ArrayList<String>(ARRAY_DEFAULT_SIZE);

  while (scanner.hasNext()) {
   String item = scanner.next();

   if (item.equals("exit"))
    break;
   else {
    list.add(item);
   }
  }

  String ip_array[] = new String[list.size()];
  for (int i = 0; i < ip_array.length; i++) {
   ip_array[i] = list.get(i);
  }

  sort(ip_array);

  for (int i = 0; i < ip_array.length; i++) {
   System.out.println(ip_array[i]);
  }

  scanner.close();
 }

 private static void sort(Comparable[] ip_array) {
  sort(ip_array, 0, ip_array.length - 1);
 }

 private static void sort(Comparable[] ip_array, int lo, int hi) {
  if (hi <= lo)
   return;

  int partition = partition(ip_array, lo, hi);

  sort(ip_array, lo, partition - 1);
  sort(ip_array, partition + 1, hi);
 }

 private static int partition(Comparable[] ip_array, int lo, int hi) {
  int right_index = hi+1;
  int left_index = lo;

  Comparable v = ip_array[lo];

  while (true) {

   while (isLess(ip_array[++left_index], v)) {
    if (left_index == hi)
     break;
   }

   while (isLess(v, ip_array[--right_index])) {
    if (right_index == lo)
     break;
   }

   if (right_index <= left_index)
    break;

   exch(ip_array, right_index, left_index);
  }

  exch(ip_array, lo, right_index);

  return right_index;
 }

 private static void exch(Comparable[] ip_array, int right_index, int left_index) {
  Comparable temp = ip_array[right_index];
  ip_array[right_index] = ip_array[left_index];
  ip_array[left_index] = temp;

 }

 private static boolean isLess(Comparable a, Comparable b) {
  return a.compareTo(b) < 0;
 }
}
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)