(a) Write a computer program to generate 10,000 integers ranging from 1 to 9999

Question

(a) Write a computer program to generate 10,000 integers ranging from 1 to 9999 (using a random number generator). These integers should be generated by the program at run time and stored in local memory.

(b) Write computer programs to sort these numbers in the increasing order using the following algorithms
(i) Quick sort
(ii) Merge sort
(iii) Bubble sort

In the computer program use a command which printouts the computer time used.

(c) Rerun the programs by generating 100,000 integers ranging from 1 to 99999. See if you are able to make some conclusions about the efficiency of various sorting approaches.

Please submit C++ programs. Take care if you use C++, avoid non-standard or windows specific libraries. Programs that cannot build or run will receive zero credit.

Explanation / Answer

/* rand example: guess the number */
#include <stdio.h> /* time */
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */

#define MAX_ARRAY_SIZE 50000

void quick(int a[],int l, int u)
{
int p,temp,i,j;
if(l<u)
{
p=a[l];
i=l;
j=u;
while(i<j)
{
while(a[i] <= p && i<j )
   i++;
while(a[j]>p && i<=j )
   j--;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;}
}
temp=a[j];
a[j]=a[l];
a[l]=temp;
quick(a,l,j-1);
quick(a,j+1,u);
}
}

void merge(int *a, int low, int high, int mid)
{
int i, j, k, c[MAX_ARRAY_SIZE];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[i];
k++;
i++;
}
while (j <= high)
{
c[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}

void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}

void bubbleSort(int arr[], int n) {
int swapped = 1;
int j = 0;
int tmp;
while (swapped) {
swapped = 0;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = 1;
}
}
}
}

void main()
{
int n[MAX_ARRAY_SIZE],m[MAX_ARRAY_SIZE],k[MAX_ARRAY_SIZE];
char *date;
time_t timer;

timer=time(NULL);
date = asctime(localtime(&timer));
printf("Current Date/Time when the program started: %s ", date);  

/* initialize random seed: */
srand (time(NULL));

/* generate secret number between 1 and 10: */
for(int i=0;i<MAX_ARRAY_SIZE;i++){
    n[i]= rand() % MAX_ARRAY_SIZE + 1;
   m[i]= n[i];
   k[i]= m[i];
}
int l=0;
int u=MAX_ARRAY_SIZE-1;
timer=time(NULL);
date = asctime(localtime(&timer));
printf("Current Date/Time to generate random numbers: %s ", date);  
quick(n,l,u);
timer=time(NULL);
date = asctime(localtime(&timer));
printf("Current Date/Time after quick sort: %s ", date);  
mergesort(m, l,u);
timer=time(NULL);
date = asctime(localtime(&timer));
printf("Current Date/Time ager Merge sort: %s ", date);  
bubbleSort(m,MAX_ARRAY_SIZE);
timer=time(NULL);
date = asctime(localtime(&timer));
printf("Current Date/Time after Bubble Sort: %s ", date);  

printf("Enter any character to exit");  

char c;
scanf("%c",&c);
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.