Respuesta :
Answer:
Check the explanation
Explanation:
#include<iostream.h>
#include<algorithm.h>
#include<climits.h>
#include<bits/stdc++.h>
#include<cstring.h>
using namespace std;
int partition(int arr[], int l, int r, int k);
int kthSmallest(int arr[], int l, int r, int k);
void quickSort(int arr[], int l, int h)
{
if (l < h)
{
// Find size of current subarray
int n = h-l+1;
// Find median of arr[].
int med = kthSmallest(arr, l, h, n/2);
// Partition the array around median
int p = partition(arr, l, h, med);
// Recur for left and right of partition
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
int findMedian(int arr[], int n)
{
sort(arr, arr+n); // Sort the array
return arr[n/2]; // Return middle element
}
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
int n = r-l+1; // Number of elements in arr[l..r]
// Divide arr[] in groups of size 5, calculate median
// of every group and store it in median[] array.
int i, median[(n+4)/5]; // There will be floor((n+4)/5) groups;
for (i=0; i<n/5; i++)
median[i] = findMedian(arr+l+i*5, 5);
if (i*5 < n) //For last group with less than 5 elements
{
median[i] = findMedian(arr+l+i*5, n%5);
i++;
}
int medOfMed = (i == 1)? median[i-1]:
kthSmallest(median, 0, i-1, i/2);
int pos = partition(arr, l, r, medOfMed);
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left
return kthSmallest(arr, l, pos-1, k);
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int l, int r, int x)
{
// Search for x in arr[l..r] and move it to end
int i;
for (i=l; i<r; i++)
if (arr[i] == x)
break;
swap(&arr[i], &arr[r]);
// Standard partition algorithm
i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]);
return i;
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver program to test above functions
int main()
{
float a;
clock_t time_req;
int arr[] = {1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout << "Sorted array is\n";
printArray(arr, n);
time_req = clock();
for(int i=0; i<200000; i++)
{
a = log(i*i*i*i);
}
time_req = clock()- time_req;
cout << "Processor time taken for multiplication: "
<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
// Using pow function
time_req = clock();
for(int i=0; i<200000; i++)
{
a = log(pow(i, 4));
}
time_req = clock() - time_req;
cout << "Processor time taken in pow function: "
<< (float)time_req/CLOCKS_PER_S
return 0;
}
..................................................................................................................................................................................................................................................................................................................................
OR
.......................
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Swap utility
void swap(long int* a, long int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
// Bubble sort
void bubbleSort(long int a[], long int n)
{
for (long int i = 0; i < n - 1; i++) {
for (long int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
}
}
}
}
// Insertion sort
void insertionSort(long int arr[], long int n)
{
long 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;
}
}
// Selection sort
void selectionSort(long int arr[], long int n)
{
long int i, j, midx;
for (i = 0; i < n - 1; i++) {
// Find the minimum element in unsorted array
midx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
midx = j;
// for plotting graph with integer values
printf("%li, %li, %li, %li\n",
n,
(long int)tim1[it],
(long int)tim2[it],
(long int)tim3[it]);
// increases the size of array by 10000
n += 10000;
}
return 0;
}
Answer:
See explaination
Explanation:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Swap utility
void swap(long int* a, long int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
// Bubble sort
void bubbleSort(long int a[], long int n)
{
for (long int i = 0; i < n - 1; i++) {
for (long int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
}
}
}
}
// Insertion sort
void insertionSort(long int arr[], long int n)
{
long 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;
}
}
// Selection sort
void selectionSort(long int arr[], long int n)
{
long int i, j, midx;
for (i = 0; i < n - 1; i++) {
// Find the minimum element in unsorted array
midx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
midx = j;
// Swap the found minimum element
// with the first element
swap(&arr[midx], &arr[i]);
}
}
// Driver code
int main()
{
long int n = 10000;
int it = 0;
// Arrays to store time duration
// of sorting algorithms
double tim1[10], tim2[10], tim3[10];
printf("A_size, Bubble, Insertion, Selection\n");
// Performs 10 iterations
while (it++ < 10) {
long int a[n], b[n], c[n];
// generating n random numbers
// storing them in arrays a, b, c
for (int i = 0; i < n; i++) {
long int no = rand() % n + 1;
a[i] = no;
b[i] = no;
c[i] = no;
}
// using clock_t to store time
clock_t start, end;
// Bubble sort
start = clock();
bubbleSort(a, n);
end = clock();
tim1[it] = ((double)(end - start));
// Insertion sort
start = clock();
insertionSort(b, n);
end = clock();
tim2[it] = ((double)(end - start));
// Selection sort
start = clock();
selectionSort(c, n);
end = clock();
tim3[it] = ((double)(end - start));
// type conversion to long int
// for plotting graph with integer values
printf("%li, %li, %li, %li\n",
n,
(long int)tim1[it],
(long int)tim2[it],
(long int)tim3[it]);
// increases the size of array by 10000
n += 10000;
}
return 0;
}
