CS 15-121 Introduction to Data Structures         Lab-10 

QuickSort

	1. Copy the following code for quicksort.
	2. Sort these numbers on paper : 9,7,5,11,12,2,14,3,10,6 while following the logic in the code.
	

HeapSort
	1. Copy the following code for heapsort.
	2. Sort these numbers on paper : 15,19,10,7,17,16. Draw both the array and tree representation for each step.
	

For both the above programs, create large arrays of different sizes. Print out the time taken in milliseconds for the sort to work on these inputs. You can do this by starting a timer before and after sorting the elements. Figure out which sort is generally better after testing on arrays of various sizes.

******************************QuickSort****************************

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class QSortAlgorithm {
    static void sort(Integer a[], int lo0, int hi0) throws Exception {
	int lo = lo0;
	int hi = hi0;
        //stopping condition
	if (lo >= hi) {
	    return;
	}
        else if( lo == hi - 1 ) {
            /*
             *  sort a two element list by swapping if necessary 
             */
            if (a[lo] > a[hi]) {
                int T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }
            return;
	}


        /*
         *  Pick a pivot and move it out of the way
         */
	int pivot = a[(lo + hi) / 2];
        a[(lo + hi) / 2] = a[hi];
        a[hi] = pivot;

        while( lo < hi ) {
            /*
             *  Search forward from a[lo] until an element is found that
             *  is greater than the pivot or lo >= hi 
             */
            while (a[lo] <= pivot && lo < hi) {
		lo++;
	    }

            /*
             *  Search backward from a[hi] until element is found that
             *  is less than the pivot, or lo >= hi
             */
	    while (pivot <= a[hi] && lo < hi ) {
		hi--;
	    }

            /*
             *  Swap elements a[lo] and a[hi]
             */
            if( lo < hi ) {
                int T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }

	
	}

        /*
         *  Put the median in the "center" of the list
            */
        a[hi0] = a[hi];
        a[hi] = pivot;

        /*
         *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
         *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
         *  pivot.
         */
      
	sort(a, lo0, lo-1);
	sort(a, hi+1, hi0);
       
    }

    static void sort(Integer a[]) throws Exception {
	sort(a, 0, a.length-1);
    }
    
    public static void main(String args[]) throws Exception
    {
       
        System.out.println(System.currentTimeMillis());
        Integer []a = new Integer[]{9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        sort(a);        
    }
}


*****************************HeapSort***********************************

public class HeapSort 
{    
    private static int N;
    /* Sort Function */
    public static void sort(Integer arr[])
    {       
        heapify(arr);        
        for (int i = N; i > 0; i--)
        {
            swap(arr,0, i);
            N = N-1;
            maxheap(arr, 0);
        }
    }     
    /* Function to build a heap */   
    public static void heapify(Integer arr[])
    {
        N = arr.length-1;
        for (int i = N/2; i >= 0; i--)
            maxheap(arr, i);        
    }
    /* Function to swap largest element in heap */        
    public static void maxheap(Integer arr[], int i)
    { 
        int left = 2*i ;
        int right = 2*i + 1;
        int max = i;
        if (left <= N && arr[left] > arr[i])
            max = left;
        if (right <= N && arr[right] > arr[max])        
            max = right;
 
        if (max != i)
        {
            swap(arr, i, max);
            maxheap(arr, max);
        }
    }    
    /* Function to swap two numbers in an array */
    public static void swap(Integer arr[], int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp; 
    }    
    /* Main method */
    public static void main(String[] args) 
    {
        
        Integer arr[] = new Integer[]{15,19,10,7,17,16};
        sort(arr);
        /* Print sorted Array */
        System.out.println("\nElements after sorting ");        
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i]+" ");            
        System.out.println();            
    }    
}