[Java] HeapSort with Linked List

1. 
   
2. /**
3.  * @author Kong Yin Lam - NMC Year2 Student - 17/11/2015
4.  */
5. 
   
6. import java.util.*;
7. public class HeapSortWithLinkedList {
8. 
   
9.     public static void main(String[] args) {
10.      
11.         int totalOfelement = 10;                   // assume the total of elements
12.         /* --------------------------------------------------------------------*/
13.         LinkedList list = new LinkedList();        // creat a LinkedList object
14.         Random rand = new java.util.Random();
15.         for(int i=0; i<totalOfelement; i++){
16.            list.addItem(rand.nextInt(100));        // add number into LinkedList
17.         }
18.         /* --------------------------------------------------------------------*/
19.         System.out.print("unsorted :\t");
20.         list.printAll();                           // print a unsorted set of numbers
21.         /* --------------------------------------------------------------------*/
22.         System.out.print("\nsorted\t :\t");
23.         HeapSort hs = new HeapSort();              // creat a HeapSort object
24.                  hs.init(list);                    // pass linked list for initialization
25.                  hs.startSort();                   // start heap sorting
26.                
27.         list.printAll();                           // print a sorted set of numbers
28.     }
29. }
30. 
    
31. class HeapSort{
32.    private LinkedList list;
33.    private int length;
34.    public HeapSort(){}
35.    public void init(LinkedList list){
36.       this.list = list;
37.       this.length = list.returnLength();
38.    }
39.    public void startSort(){
40.           for(int i=length/2-1; i>=0; i--){
41.                heapify(i, length);  
42.           }
43.           for(int i=length-1; i>0 ; i--){
44.                swap(0, i);           // swap the first element(biggest) to the sorted group in each time
45.                heapify(0, i);        // check maxHeap's properties with unsorted group
46.           }
47.    }
48.    public void heapify(int root, int length){
49.        int left = root*2+1;          // left Child  -> n*2+1
50.        int right = root*2+2;         // Right Child -> n*2+2
51.        int maxHeap = root;           // assume root is largest
52.      
53.        /* check whether it fulfills the maxHeap's properties */
54.        maxHeap = left<length && list.returnNodeByIndex(left).returnValue()>list.returnNodeByIndex(maxHeap).returnValue() ? left : maxHeap;
55.        maxHeap = right<length &&list.returnNodeByIndex(right).returnValue()>list.returnNodeByIndex(maxHeap).returnValue() ? right : maxHeap;
56.      
57.        if(maxHeap!=root){            // It means not fulfill
58.           swap(root, maxHeap);       // swap
59.           heapify(maxHeap, length);  // check again
60.        }      
61.    }
62.    public void swap(int i, int j){
63.         int tmp = list.returnNodeByIndex(i).returnValue();
64.         list.returnNodeByIndex(i).setValue(list.returnNodeByIndex(j).returnValue());
65.         list.returnNodeByIndex(j).setValue(tmp);
66.    }
67. }
68. 
    
69. class LinkedList{
70.     private Node head;
71.     private int length;
72.     public LinkedList(){}
73.     public void addItem(int value){
74.          if(length==0)     // It means no element in the list
75.              head = new Node(value);    
76.          else
77.              this.returnLastNode().appendNode(new Node(value));
78.          length++;
79.     }
80.     public Node returnLastNode(){
81.         Node tmp = head;
82.         while(tmp.returnNext()!=null){
83.             tmp = tmp.returnNext();
84.         }
85.         return tmp;
86.     }
87.     public void printAll(){
88.         Node tmp = head;
89.         for(int i=0; i<length; i++){
90.            System.out.print(tmp.returnValue()+"\t");
91.            tmp=tmp.returnNext();
92.         }
93.     }
94.     public Node returnNodeByIndex(int index){
95.         Node tmp = head;
96.         for(int i=0; i<index; i++){
97.             tmp = tmp.returnNext();
98.         }
99.         return tmp;
100.     }
101.     public int returnLength(){
102.         return this.length;
103.     }
104. }
105. 
     
106. class Node{
107.     private Node next;
108.     private int value;
109.     public Node(int value){
110.           next=null;
111.           this.value = value;
112.     }
113.     public void appendNode(Node node){this.next = node;}
114.     public void setValue(int value){this.value = value;}
115.     public Node returnNext(){return this.next;}
116.     public int returnValue(){return this.value;}
117. }
118.    
119.