# Assignment V Solution

\$30.00

Category:

## Description

A. Let n denote the size of an array A (of integers) which we want to sort.

The performance of quick sort is very sensitive to the initial distribution of A and also to the choice of the pivot. We need to work with random, sorted, and almost sorted arrays. Also, the following ways of choosing the pivot for partitioning is to be experimented with.

 FIRST Choose the first element A[0] as the pivot. RANDOM Choose A[r] as the pivot for a random r ∈ {0, 1, 2, . . . , n − 1}. MEDIAN OF THREE Choose r, s,t ∈ {0, 1, 2, . . . , n − 1}, and take the median of A[r], A[s], A[t] as the pivot. Use both the following choices for r, s,t. (1) r = 0, s = n/2, and t = n − 1. (2) r = n/4, s = n/2, and t = 3n/4.

Write a function quicksort(A, n, pivot type) to sort an array A with n (non-negative) integers. The third argument pivot type indicates how you choose the pivot for partitioning:

0 means FIRST,

1 means RANDOM,

2 means MEDIAN OF THREE (1), and

3 means MEDIAN OF THREE (2).

In the main() function

For n = 10k , k = 4, 5, 6, 7, and for each choice of the pivot type, repeat the following:

Populate an array A with n random integers in the range 0 to 109 −1. The random choices of elements may lead to repetitions. You do not need to avoid repetitions. Sort A by calling quicksort. Now, A is sorted. Call quicksort again on this sorted array. Now, swap a few elements in A (take k = n/100, and swap k randomly chosen pairs of A). This gives you an almost sorted array. Run quicksort again on this array. Report the times taken by the three calls. Do not include the array-preparation times.

A random integer in the range [0, 109 − 1] can be generated by the call ( #include <stdlib.h> ):

A[i] = rand() % 1000000000;

Different runs of your program should handle different random sequences. In order to achieve that, write the following line at the beginning of your main() function. You need to include <stdlib.h> and <time.h> .

srand((unsigned int)time(NULL));

Finally, this is how you can measure (calendar) times in C programs (include <time.h> ).

clock_t c1, c2;

double runtime;

c1 = clock();

<- – – Code for which the running time is to be measured – – ->

c2 = clock();

runtime = (double)(c2 – c1) / (double)CLOCKS_PER_SEC; /* Time in seconds */

SAMPLE OUTPUT : Present your output in the following format.

Performance of Quick Sort

 n Pivot type Random Sorted Almost Sorted 10000 FIRST 0.001 0.002 0.002 10000 RANDOM 0.001 0.001 0.001 10000 MEDIAN OF THREE 1 0.001 0.002 0.001 10000 MEDIAN OF THREE 2 0.001 0.000 0.001 100000 FIRST – – – 100000 RANDOM – – – 100000 MEDIAN OF THREE 1 – – – 100000 MEDIAN OF THREE 2 – – – 1000000 FIRST – – – 1000000 RANDOM – – – 1000000 MEDIAN OF THREE 1 – – – 1000000 MEDIAN OF THREE 2 – – – 10000000 FIRST – – – 10000000 RANDOM – – – 10000000 MEDIAN OF THREE 1 – – – 10000000 MEDIAN OF THREE 2 – – –

1. You are given name of few test cricket players with their runs in international test cricket career. Sort the player in ascending order based on their score. If scores of more than one player is same then order those players in lexicographical order (when you try to sort name in lexicographical order , find out the name with minimum characters let’s say it is m then consider first m characters of all the words of which you have to break the tie). Use linear sorting algorithm.

Dravid13288

Gambhir11953

Ponting 13378 jayawardene 11814

Lara11953

Kallis 13289 Chanderpaul 11867

Tendulkar15921

Gooch13289

Cook 1586 Sangakkara 12400

Sarwan11953

IRBell13289