Thursday, December 24, 2015

Heap 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
/**
 * 
 * 
 * Time Complexity: O(nLogn)
 * 
 * 
 * Note:
 *   - Heap sort is an in-place algorithm.
 *   - 
 * 
 * Application
 *   - Priority Queues
 * 
 * @author ramesh
 *
 */
public class Heapsort {
 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[] a) {
  int N = a.length;
  for (int i = N / 2; i >= 1; i--) {
   sink(a, i, N);
  }

  while (N > 1) {
   exch(a, 1, N--);
   sink(a, 1, N);
  }
 }

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

 private static void sink(Comparable[] a, int k, int N) {
  while (k * 2 <= N) {
   int j = k * 2;
   if (j < N && isLess(a, j, j + 1))
    j++;
   if (!isLess(a, k, j))
    break;
   exch(a, j, k);
   k = j;
  }
 }

 private static boolean isLess(Comparable[] pq, int i, int j) {
  return pq[i - 1].compareTo(pq[j - 1]) < 0;
 }
}

Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)