Question

Description: The goal of this assignment is to compare the empirical complexity of two sorting algorithms: a) Heap sort and b) Radix sort.

Instructions:

- Implement the above two sorting algorithms using Java or any other programming language.

- Repeatedly generate random input instances containing 10, 50, 100, 500, 1000, 5000, 10000, 15000, … 50 000. The generated numbers must be between 0 and 100.

- Execute both algorithms to sort the randomly generated arrays.

- Compare the running time of both algorithms and validate their theoretical complexity.

Comment your source code and upload it along with a Word document presenting your results. The report should contain plots illustrating the obtained results and facilitating the comparison of the time complexity of both algorithms.

Hints: The theoretical time complexity for a Heap sort algorithm is O (n log n) and O(d(n+b)) for the Radix sort. As above indicated, b is 10 and d is 3. Considering that configuration, the empirical time complexity of Radix sort should be better than the Heap sort.

Extra: Empirical Study of the impact of d

What if the randomly generated numbers become between 0 and 10 000000 instead of 0-100. Will the Radix algorithm continue to perform better than heap sort? If not, what is the value of d at which Heap sort becomes better than Radix sort. Vary d and re-plot the performance of both algorithms.

Answer 1

a. HEAP SORT

1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
3. Repeat step 2 while size of heap is greater than 1.

b. RADIX SORT

1. Find the largest number in ARR as LARGE

2. [INITIALIZE] SET NOP = Number of digits in LARGE

3. SET PASS =0

4. Repeat Step 5 while PASS <= NOP-1

5. SET I = 0 and INITIALIZE buckets

6. Repeat Steps 7 to 9 while I

7. SET DIGIT = digit at PASSth place in A[I]

8. Add A[I] to the bucket numbered DIGIT

9. INCREMENT bucket count for bucket numbered DIGIT
[END OF LOOP]

10. Collect the numbers in the bucket
[END OF LOOP]

11. END

What is the running time of Heap Sort?

Time complexity of heapify is O(Logn). Time complexity of createAndBuildHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).

What is the running time of Radix Sort?

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for the decimal system, b is 10.If k is the maximum possible value, then d would be O(log_b(k)). So overall time complexity is O((n+b) * log_b(k))

Let k <= n^c where c is a constant. In that case, the complexity becomes O(nLog_b(n)). But it still doesn’t beat comparison-based sorting algorithms.
What if we make the value of b larger?. What should be the value of b to make the time complexity linear? If we set b as n, we get the time complexity as O(n). In other words, we can sort an array of integers with a range from 1 to n^c if the numbers are represented in base n (or every digit takes log₂(n) bits).

for d<= 3 radix sort is better that heap sort but for d>=3 heap sort is better than radix sort

Heap Sort

import java.util.Random;

public class HeapSort

{

    public void sort(int arr[])

    {

        int n = arr.length;

  

        // Build heap (rearrange array)

        for (int i = n / 2 - 1; i >= 0; i--)

            heapify(arr, n, i);

  

        // One by one extract an element from heap

        for (int i=n-1; i>0; i--)

        {

            // Move current root to end

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

  

            // call max heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

  

    // To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap

    void heapify(int arr[], int n, int i)

    {

        int largest = i; // Initialize largest as root

        int l = 2*i + 1; // left = 2*i + 1

        int r = 2*i + 2; // right = 2*i + 2

  

        // If left child is larger than root

        if (l < n && arr[l] > arr[largest])

            largest = l;

  

        // If right child is larger than largest so far

        if (r < n && arr[r] > arr[largest])

            largest = r;

  

        // If largest is not root

        if (largest != i)

        {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

  

            // Recursively heapify the affected sub-tree

            heapify(arr, n, largest);

        }

    }

  

    static void printArray(int arr[]) /* A function to print array of size n */

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i]+" ");

        System.out.println();

    }

  

    // Driver program

    public static void main(String args[])

    {

        

        Random rand = new Random(); //instance of random class

      int upperbound = 100;

      int []arr= new int[100]

      for(int i =0; i<100; i++)

        arr[i] = rand.nextInt(upperbound);

        int n = arr.length;

  

        HeapSort ob = new HeapSort();

        ob.sort(arr);

  

        System.out.println("Sorted array is");

        printArray(arr);

    }

}

RADIX SORT

import java.util.Random;

public class Radix_Sort {  

public static void main(String[] args) {  

        int i;  

          Random rand = new Random(); //instance of random class

      int upperbound = 100;

      int []arr= new int[100]

      for(int i =0; i<100; i++)

        arr[i] = rand.nextInt(upperbound);

        int n = arr.length;

        radix_sort(a);    

        System.out.println("\n The sorted array is: \n");  

        for(i=0;i<10;i++)  

            System.out.println(a[i]);  

    }  

  

    static int largest(inta[])  

    {     

        int larger=a[0], i;   

        for(i=1;i<10;i++)  

        {  

            if(a[i]>larger)  

            larger = a[i];  

        }  

        returnlarger;  

    }  

    static void radix_sort(inta[])  

    {  

        int bucket[][]=newint[10][10];  

        int bucket_count[]=newint[10];  

        int i, j, k, remainder, NOP=0, divisor=1, larger, pass;  

        larger = largest(a);  

        while(larger>0)  

        {  

            NOP++;  

            larger/=10;  

        }  

        for(pass=0;pass<NOP;pass++) // Initialize the buckets  

        {  

            for(i=0;i<10;i++)  

            bucket_count[i]=0;  

            for(i=0;i<10;i++)  

            {  

                // sort the numbers according to the digit at passth place            

                remainder = (a[i]/divisor)%10;  

                bucket[remainder][bucket_count[remainder]] = a[i];  

                bucket_count[remainder] += 1;  

            }  

            // collect the numbers after PASS pass  

            i=0;  

            for(k=0;k<10;k++)  

            {  

                for(j=0;j<bucket_count[k];j++)  

                {  

                    a[i] = bucket[k][j];  

                    i++;  

                }  

            }  

            divisor *= 10;  

        }  

    }  

}