`Sort a given set of n integer elements using the Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus a non graph sheet. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.

1 package sortingAlgorithms.mergeSort;
2
3 /**
4 * @author CSE, BIET
5 *
6 */
7
8 public class TopDownMergeSort {
9
10         public void topDownMergeSort(int[] a, int[] b, int n)
11         {
12          copyArray(a, 0, n, b);
13          topDownSplitMerge(b, 0, n, a);
14         }
15
16         void topDownSplitMerge(int[] b, int iBegin, int iEnd, int[] a)
17         {
18          if (iEnd - iBegin <= 1)
19          return;
20
21          int iMiddle = (iEnd + iBegin) / 2;
22
23          topDownSplitMerge(a, iBegin, iMiddle, b);
24          topDownSplitMerge(a, iMiddle, iEnd, b);
25
26          topDownMerge(b, iBegin, iMiddle, iEnd, a);
27         }
28
29         void topDownMerge(int[] a, int iBegin, int iMiddle, int iEnd, int[] b)
30         {
31          int i = iBegin;
32          int j = iMiddle;
33
34
35          for (int k = iBegin; k < iEnd; k++) {
36
37          if (i < iMiddle && (j >= iEnd || a[i] <= a[j])) {
38          b[k] = a[i];
39          i = i + 1;
40          } else {
41          b[k] = a[j];
42          j = j + 1;
43          }
44          }
45         }
46
47         public void copyArray(int[] a, int iBegin, int iEnd, int[] b)
48         {
49          for (int k = iBegin; k < iEnd; k++)
50          b[k] = a[k];
51         }
52
53
54 }
55
56
57 package sortingAlgorithms.mergeSort;
58
59 import java.util.Arrays;
60 import java.util.Random;
61 import java.util.Scanner;
62
63 public class MergeSortDemo {
64
65         public static void calculateExecutionTime() {
66                 System.out.println("\n\nRunning time of Merge Sort:");
67                 System.out.println("\n\nN\tRepetitions\tTime");
68                 System.out.println("-------------------------------");
69
70                 TopDownMergeSort tSort = new TopDownMergeSort();
71
72                 int step = 2000;
73                 for (int n = 5000; n < 50000; n += step) {
74                         Random rn = new Random();
75                         int[] a = new int[n];
76                         int[] b = new int[n];
77
78                         /* get time for size n */
79                         long repetitions = 0;
80                         long start = System.nanoTime();
81
82                         do {
83                                 repetitions++;
84                                 for (int i = 0; i < n; ++i)
85                                         a[i] = rn.nextInt(n); // i // n - i
86
87                                 tSort.topDownMergeSort(a, b, n);
88
89                         } while (System.nanoTime() - start < 1000000000);
90
91                         /* repeat until enough time has elapsed */
92                         double duration = ((double) (System.nanoTime() - start)) / 1000000000;
93                         duration /= repetitions;
94
95                         System.out.printf("%d\t%d\t\t%.4f\n", n, repetitions, duration);
96
97                 }
98
99         }
100
101        public static void main(String[] args) {
102
103                Scanner input = new Scanner(System.in);
104
105                System.out.println("Enter the Size of an Array: ");
106                int iBegin = 0;
107                int iEnd = input.nextInt();
108
109                System.out.println("System automatically generates numbers ");
110
111                Random rn = new Random();
112                int[] a = new int[iEnd];
113                int[] b = new int[iEnd];
114
115                for (int i = 0; i < iEnd; ++i) {
116                        a[i] = rn.nextInt(iEnd);
117                }
118
119                System.out.println("Before: ");
120                System.out.println("MergeSort [A[]=" + Arrays.toString(a) + "]");
121
122                TopDownMergeSort tSort = new TopDownMergeSort();
123
124                tSort.topDownMergeSort(a, b, iEnd);
125
126                System.out.println("After: ");
127                System.out.println("MergeSort [A[]=" + Arrays.toString(a) + "]");
128
129                calculateExecutionTime();
130
131        }
132
133}

OUTPUT:

Enter the Size of an Array:

System automatically generates numbers

Before:

MergeSort [A[]=[3, 8, 6, 7, 1, 7, 8, 4, 9, 2]]

After:

MergeSort [A[]=[1, 2, 3, 4, 6, 7, 7, 8, 8, 9]]

Input Size	Random Numbers		Increasing Order		Decreasing Order
Input Size	Repetitions	Time	Repetitions	Time	Repetitions	Time
5000	1688	0.0006	7065	0.0001	6217	0.0002
7000	1101	0.0009	5016	0.0002	4348	0.0002
9000	887	0.0011	3859	0.0003	3285	0.0003
11000	643	0.0016	3126	0.0003	2198	0.0005
13000	554	0.0018	2536	0.0004	1862	0.0005
15000	426	0.0024	2156	0.0005	1643	0.0006
17000	435	0.0023	1881	0.0005	1386	0.0007
19000	356	0.0028	1679	0.0006	1389	0.0007
21000	353	0.0028	1522	0.0007	1213	0.0008
23000	315	0.0032	1128	0.0009	1031	0.001
25000	293	0.0034	1215	0.0008	970	0.001
27000	234	0.0043	1098	0.0009	916	0.0011
29000	245	0.0041	1065	0.0009	825	0.0012
31000	199	0.005	1000	0.001	834	0.0012
33000	193	0.0052	948	0.0011	801	0.0012
35000	154	0.0065	883	0.0011	732	0.0014
37000	177	0.0057	832	0.0012	687	0.0015
39000	159	0.0063	784	0.0013	623	0.0016
41000	144	0.007	749	0.0013	563	0.0018
43000	138	0.0073	688	0.0015	588	0.0017
45000	127	0.0079	622	0.0016	533	0.0019
47000	126	0.0079	578	0.0017	524	0.0019
49000	127	0.0079	568	0.0018	513	0.002

The Learning Network

Program 5 MergSort Demo

No comments:

Post a Comment

Online Certifications

Report Abuse

Labels