Assignment V Solution

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





















Upload file Assign5A.c




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




Gavaskar10122




Ponting 13378 jayawardene 11814




Lara11953




Kallis 13289 Chanderpaul 11867




Tendulkar15921




Gooch13289




Cook 1586 Sangakkara 12400




Sarwan11953




IRBell13289










Upload file Assign5B.c