C++ Assignment Make sure to implement proper coding conventions to receive full

Question

C++ Assignment Make sure to implement proper coding conventions to receive full credit. Execute each subtask and complete the analysis table below. Make sure source code and output are clearly visible. Functions or classes are ok, the time analysis after the successful implementation of each sort is critical to receiving the full credit. ART 1 Task 1: Functions or classes are ok. Create an array that holds 1000 random floats between 1-1000. implement Selection sort to sort the values in ascending order. Least Greatest Measure the time it takes to execute the sort in milliseconds. Please run the sort 3 times. Attach Photos of Source Code and Output . Task 2: Functions or classes are ok Create an array that holds 1000 random floats between 1-1000. Implement insertion sort to sort the values in ascending order. Least-> Greatest Measure the time it takes to execute the sort in milliseconds. Please run the sort 3 times. Attach Photos of Source Code and Output . Task 3: Functions or classes are ok. Create an array that holds 1000 random floats between 1-1000. Implement Quick Sort to sort the values in ascending order. Least Greatest Measure the time it takes to execute the sort in milliseconds. Please run the sort 3 times. Attach Photos of Source Code and Output .

Explanation / Answer

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

int arr[10000], n;

void swap(int *xp, int *yp);
void in_sort(int *arr,int n);
void sel_sort(int *arr,int n);

int partition(int arr[], int m, int p);

void interchange(int arr[], int i, int j);

void QuickSort(int arr[], int p, int q);

int main()

{

// int arr[100], n;

int i;

time_t start, end,t;

time_t diff;

printf(" Enter the number of elements: ");

scanf("%d", &n);

srand((unsigned) time(&t));

//Generates random elements

// printf(" Enter the elements: ");

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

{

// scanf("%d", &a[i]);

arr[i]=rand()%n;
}

printf(" The elements are ");

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

{

printf("%d ", arr[i]);

}

clock_t tic = clock();
//start=time(NULL);

for(int m=0;m<3;m++){

QuickSort(arr, 0, n-1);
in_sort(arr,n);
sel_sort(arr,n);
}
//end=time(NULL);

//diff=difftime(end, start);

clock_t toc = clock();

printf(" The sorted array is ");

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

printf("%d ", arr[i]);

//printf(" Time taken is %ld seconds", diff);
printf("Elapsed: %f seconds ", (double)(toc - tic) / CLOCKS_PER_SEC);

return 0;

}

//-------FIND THE POSITION OF THE PARTITION-------

int partition(int arr[], int m, int p)

{

int v=arr[m];

int i=m;

int j=p;

do

{

do

i++;

while(arr[i]<v);

do

j--;

while(arr[j]>v);

if(i<j)

interchange(arr, i, j);

}while(i<=j);

arr[m]=arr[j];

arr[j]=v;

return j;

}

//-------INTERCHANGE THE ELEMENTS-------

void interchange(int arr[], int i, int j)

{

int p;

p=arr[i];

arr[i]=arr[j];

arr[j]=p;

}

//-------QUICK SORT-------

void QuickSort(int arr[], int p, int q)

{

int j, k, temp;

if(p<q) //If there are more than 1 element, divide p into 2 sub-problems

{

k=rand() % (q-p+1)+p;

interchange(arr, k, p);

/* temp=arr[k];

arr[k]=arr[p];

arr[p]=temp; */

j=partition(arr, p, q+1); //j is the position of partioning element

//Solve sub-problems

QuickSort(arr, p, j-1);

QuickSort(arr, j+1, q);

}

}

void in_sort(int *arr,int n){

int i, key, j;

for (i = 1; i < n; i++){

key = arr[i];

j = i-1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key){

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

}
}

void sel_sort(int *arr,int n){
int i, j, min_idx;

// One by one move boundary of unsorted subarray

for (i = 0; i < n-1; i++){

// Find the minimum element in unsorted array

min_idx = i;

for (j = i+1; j < n; j++){

if (arr[j] < arr[min_idx]){

min_idx = j;

// Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);
}

}
}
}

void swap(int *xp, int *yp){

int temp = *xp;

*xp = *yp;

*yp = temp;

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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