Sort an array of 10,000 elements using the quick sort algorithm as follows: a. S
ID: 3692416 • Letter: S
Question
Sort an array of 10,000 elements using the quick sort algorithm as follows:
a. Sort the array using pivot as the middle element of the array.
b. Sort the array using pivot as the median of the first, last, and middle elements of the array.
c. Sort the array using pivot as the middle element of the array. However, when the size of any sublist reduces to less than 20, sort the sublist using an insertion sort.
d. Sort the array using pivot as the median of the first, last, and middle elements of the array. When the size of any sublist reduces to less than 20, sort the sublist using an insertion sort.
e. Calculate and print the CPU time for each of the preceding four steps. To find the current CPU time, declare a variable, say, x, of type clock t. The statement x = clock(); stores the current CPU time in x. You can check the CPU time before and after a particular phase of a program. Then, to find the CPU time for that particular phase of the program, subtract the before time from the after time. Moreover, you must include the header file ctime to use the data type clock t and the function clock. Use a random number generator to initially fill the array.
Explanation / Answer
program :
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void random_shuffle(int arr[])
{
srand(time(NULL));
int i, j, temp;
for (i = MAX - 1; i > 0; i--)
{
j = rand()%(i + 1);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partion(int arr[], int p, int r)
{
int pivot = arr[r];
int i = p - 1;
int j;
for (j = p; j < r; j++)
{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[r]);
return i + 1;
}
void quick_sort(int arr[], int p, int q)
{
int j;
if (p < q)
{
j = partion(arr, p, q);
quick_sort(arr, p, j - 1);
quick_sort(arr, j + 1, q);
}
}
int main()
{
int i;
int arr[MAX];
for (i = 0;i < MAX;i++)
arr[i] = i + 99999;
random_shuffle(arr);
quick_sort(arr, 0, MAX-1);
for (i = 0; i < MAX;i++)
printf("%d ", arr[i]);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.