c++ selection sort (random) Functions or classes are ok. Create an array that ho

Question

c++

selection sort (random)

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

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

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.