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;
}