Implement a random number generator function that can generate integer numbers b
ID: 651626 • Letter: I
Question
Implement a random number generator function that can generate integer numbers be- tween 1 and 20000. Duplicate numbers should not be allowed. You can make use of any of the random number generating available in C library, or you can write your own pseudo random number generating code.
Implement algorithms for insertion sort, quick sort, heap sort, and merge sort. Given a choice between a recursive and an iterative version for a particular algorithm, you may choose either one.
Execute each sorting algorithm for the following different values of n, where n is the size of the list to be sorted,
n = 100, 500, 1000, 2000, 5000, 8000, 10000.
In each case, the list consists of random numbers generated in step 1. For a particular value of n, the same input data (i.e., list to be sorted) should be given to all the sorting algorithms.
For each value of n, and for each sorting algorithm, obtain the actual execution time of the algorithm for the machine you are using for the cases when
a) an unsorted list is presented as the input data, and b) a sorted list is presented as the input data
Make sure your sorting algorithms work properly by examining the sorted data. However, do not submit any sorted data as output. No output files need to be submitted. You are required to submit the source code and an input file for size n = 100, using the submitd command.
Explanation / Answer
void sort(int[] arr){
int[] helper = new int[arr.length];
mergesort(arr, helper, 0, arr.length-1);
}
void mergesort(int[] arr, int[] helper, int low, int high){
if(low < high){
int middle = (high+low)/2;
mergesort(arr, helper, low, middle);
mergesort(arr, helper, middle+1, high);
merge(arr, helper, low, middle, high);
}
}
void merge(int[] arr, int[] helper, int low, int middle, int high){
for (int x=low; x <= high; x++) {
helper[x] = arr[x];
}
int left = low;
int curr = low;
int right = middle+1;
while(left <= middle && right <= high) {
if(helper[right] > helper[left])
arr[curr++] = helper[left++];
else
arr[curr++] = helper[right++];
}
while(left <= middle)
arr[curr++] = helper[left++];
}
def binarySearch( A, n, value ):
if n = 1:
if A[ 0 ] = value:
return true
else:
return false
if value < A[ n / 2 ]:
return binarySearch( A[ 0...( n / 2 - 1 ) ], n / 2 - 1, value )
else if value > A[ n / 2 ]:
return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 - 1, value )
else:
return true
0th iteration: n
1st iteration: n / 2
2nd iteration: n / 4
3rd iteration: n / 8
...
ith iteration: n / 2i
...
last iteration: 1
Notice that in the i-th iteration, our array has n / 2i elements.
Algorithm best average worst space complexity
Insertion Sort O(n) O(n2) O(n2) O(1)
Merge sort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.