7 Your TaskFind out the reason that commands you to write; see whether it has spreadits roots into the very depth of your heart; confess to yourself you wouldhave to die if you were forbidden to...

1 answer below »
I need help with this sorting program


7 Your Task Find out the reason that commands you to write; see whether it has spread its roots into the very depth of your heart; confess to yourself you would have to die if you were forbidden to write. —Rainer Maria Rilke Your task for this assignment is as follows: 1. Implement Shell Sort, Batcher Sort (Batcher’s method), Heapsort, and recursive Quicksort based on the provided Python pseudocode in C. The interface for these sorts will be given as the header files shell.h, batcher.h, heap.h, and quick.h. You are not allowed to modify these files for any reason. 2. Implement a test harness for your implemented sorting algorithms. In your test harness, you will creating an array of pseudorandom elements and testing each of the sorts. Your test harness must be in the file sorting. c. 3. Gather statistics about each sort and its performance. The statistics you will gather are the size of the array, the number of moves required, and the number of comparisons required. Note: a comparison is counted only when two array elements are compared. Your test harness must support any combination of the following command-line options: « -a: Employs all sorting algorithms. « -h: Enables Heap Sort. « -b: Enables Batcher Sort. « 5: Enables Shell Sort. « -q: Enables Quicksort. « -r seed: Set the random seed to seed. The default seed should be 13371453. « -n size: Set the array size to size. The default size should be 100. « -p elements : Print out elements number of elements from the array. The default number of elements to print out should be 100. If the size of the array is less than the specified number of elements to print, print out the entire array and nothing more. « -H: Prints out program usage. See reference program for example of what to print. Itis important to read this carefully. None of these options are exclusive of any other (you may specify any number of them, including zero). The most natural data structure for this problem is a set. 8 Sets For this assignment, you are required to use a set to track which command-line options are specified when your program is run. The code for sets is given in the resources repository in set .h. You may not modify this file. Make sure to take the time to go through and understand the code. For manipulating the bits in a set, we use bit-wise operators. These operators, as the name suggests, will perform an operation on every bit in a number. The following are the six bit-wise operators specified nC: & | bit-wise AND | Performs the AND operation on every bit of two numbers. |_| bit-wise OR_| Performs the OR operation on every bit of two numbers. ~ | bit-wise NOT | Inverts all bits in the given number. ~ | bit-wise XOR | Performs the exclusive-OR operation on every bit of two numbers. < |="" left="" shift="" shifts="" bits="" in="" a="" number="" to="" the="" left="" by="" a="" specified="" number="" of="" bits.="">> | right shift Shifts bits in a number to the right by a specified number of bits. Recall that the basic set operations are: membership, union, intersection and negation. The functions im- plementing these set operations are implemented for you. Using these functions, you will set (make the bit 1) or clear (make the bit 0) bits in the Set depending on the command-line options read by getopt (). You can then check the states of all the bits (the members) of the Set using a single for loop and execute the corresponding sort. Note: you most likely won't use all the functions, but you must use sets to track which command-line options are specified when running your program. Set empty_set (void) This function is used to return an empty set. In this context, an empty set would be a set in which all bits are equal to 0. bool member_set (uint32_t x, Set s) Xx €s <= xis amember of sets this function returns a bool indicating the presence of the given value x in the set s. the bit-wise and operator is used to determine set membership. the first operand for the and operation is the set s. the second operand is the value obtained by left shifting 1 x number of times. if the result of the and operation is a non-zero value, then x is a member of s and true is returned to indicate this. false is returned if the result of the and operation is 0. set insert_set(uint32_t x, set s) this function inserts x into s. that is, it returns set s with the bit corresponding to x set to 1. here, the bit is set using the bit-wise or operator. the first operand for the or operation is the set s. the second operand is value obtained by left shifting 1 by x number of bits. set delete_set(uint32_t x, set s) s—x={ylyesny#x} this function deletes (removes) x from s. that is, it returns set s with the bit corresponding to x cleared to 0. here, the bit is cleared using the bit-wise and operator. the first operand for the and operation is the set s. the second operand is a negation of the number 1 left shifted to the same position that x would occupy in the set. this means that the bits of the second operand are all 1s except for the bit at x's position. the function returns set s after removing x. set union_set (set s, set t) sut={xlxesvxet} the union of two sets is a collection of all elements in both sets. here, to calculate the union of the two sets s and t, we need to use the or operator. only the bits corresponding to members that are equal to lin either s or t are in the new set returned by the function. set intersect_set(set s, set t) snt={xlxesaxet} the intersection of two sets is a collection of elements that are common to both sets. here, to calculate the intersection of the two sets s and t, we need to use the and operator. only the bits corresponding to members that are equal to 1 in both s and t are in the new set returned by the function. set difference_set(set s, set t) the difference of two sets refers to the elements of set s which are not in set t. in other words, it refers to the members of set s that are unique to set s. the difference is calculated using the and operator where the two operands are set s and the negation of set t. the function then returns the set of elements in s that are notin t. this function can be used to find the complement of a given set as well, in which case the first operand would be the universal set u and the second operand would be the set you want to comple- ment as shown below. {xlxgs=u-s set complement_set (set s) this function is used to return the complement of a given set. by complement we mean that all bits in the set are flipped using the not operator. thus, the set that is returned contains all the elements of the universal set u that are not in s and contains none of the elements that are present in s. description 1 describe how the program works with supporting pseudocode. description 2 what you learned from the different sorting algorithms.under what conditions do sorts perorm well? under what conditions do sorts perform poorly? what conclusions can you make from your findings? graphs explaining the performance of the sorts on a variety of inputs,such as array sin reverse order, arrays with a small number of elements, and arrays with a large number of elements. your graphs must be produced using either gnuplot or matplotlib. you will find it helpful to write a script to handle the plotting. as always, awk will be helpful for parsing the output of your program. analysis of the graphs you produce. you should look carefully at any graphs that you produce. are all of the lines smooth? for example, in this graph there are some features of interest. what could be causing features that appear in your own graphs? here is an example graph produced by gnuplot with a different set of sorts for reference (axes are log-scaled): xis="" amember="" of="" sets="" this="" function="" returns="" a="" bool="" indicating="" the="" presence="" of="" the="" given="" value="" x="" in="" the="" set="" s.="" the="" bit-wise="" and="" operator="" is="" used="" to="" determine="" set="" membership.="" the="" first="" operand="" for="" the="" and="" operation="" is="" the="" set="" s.="" the="" second="" operand="" is="" the="" value="" obtained="" by="" left="" shifting="" 1="" x="" number="" of="" times.="" if="" the="" result="" of="" the="" and="" operation="" is="" a="" non-zero="" value,="" then="" x="" is="" a="" member="" of="" s="" and="" true="" is="" returned="" to="" indicate="" this.="" false="" is="" returned="" if="" the="" result="" of="" the="" and="" operation="" is="" 0.="" set="" insert_set(uint32_t="" x,="" set="" s)="" this="" function="" inserts="" x="" into="" s.="" that="" is,="" it="" returns="" set="" s="" with="" the="" bit="" corresponding="" to="" x="" set="" to="" 1.="" here,="" the="" bit="" is="" set="" using="" the="" bit-wise="" or="" operator.="" the="" first="" operand="" for="" the="" or="" operation="" is="" the="" set="" s.="" the="" second="" operand="" is="" value="" obtained="" by="" left="" shifting="" 1="" by="" x="" number="" of="" bits.="" set="" delete_set(uint32_t="" x,="" set="" s)="" s—x="{ylyesny#x}" this="" function="" deletes="" (removes)="" x="" from="" s.="" that="" is,="" it="" returns="" set="" s="" with="" the="" bit="" corresponding="" to="" x="" cleared="" to="" 0.="" here,="" the="" bit="" is="" cleared="" using="" the="" bit-wise="" and="" operator.="" the="" first="" operand="" for="" the="" and="" operation="" is="" the="" set="" s.="" the="" second="" operand="" is="" a="" negation="" of="" the="" number="" 1="" left="" shifted="" to="" the="" same="" position="" that="" x="" would="" occupy="" in="" the="" set.="" this="" means="" that="" the="" bits="" of="" the="" second="" operand="" are="" all="" 1s="" except="" for="" the="" bit="" at="" x's="" position.="" the="" function="" returns="" set="" s="" after="" removing="" x.="" set="" union_set="" (set="" s,="" set="" t)="" sut="{xlxesvxet}" the="" union="" of="" two="" sets="" is="" a="" collection="" of="" all="" elements="" in="" both="" sets.="" here,="" to="" calculate="" the="" union="" of="" the="" two="" sets="" s="" and="" t,="" we="" need="" to="" use="" the="" or="" operator.="" only="" the="" bits="" corresponding="" to="" members="" that="" are="" equal="" to="" lin="" either="" s="" or="" t="" are="" in="" the="" new="" set="" returned="" by="" the="" function.="" set="" intersect_set(set="" s,="" set="" t)="" snt="{xlxesaxet}" the="" intersection="" of="" two="" sets="" is="" a="" collection="" of="" elements="" that="" are="" common="" to="" both="" sets.="" here,="" to="" calculate="" the="" intersection="" of="" the="" two="" sets="" s="" and="" t,="" we="" need="" to="" use="" the="" and="" operator.="" only="" the="" bits="" corresponding="" to="" members="" that="" are="" equal="" to="" 1="" in="" both="" s="" and="" t="" are="" in="" the="" new="" set="" returned="" by="" the="" function.="" set="" difference_set(set="" s,="" set="" t)="" the="" difference="" of="" two="" sets="" refers="" to="" the="" elements="" of="" set="" s="" which="" are="" not="" in="" set="" t.="" in="" other="" words,="" it="" refers="" to="" the="" members="" of="" set="" s="" that="" are="" unique="" to="" set="" s.="" the="" difference="" is="" calculated="" using="" the="" and="" operator="" where="" the="" two="" operands="" are="" set="" s="" and="" the="" negation="" of="" set="" t.="" the="" function="" then="" returns="" the="" set="" of="" elements="" in="" s="" that="" are="" notin="" t.="" this="" function="" can="" be="" used="" to="" find="" the="" complement="" of="" a="" given="" set="" as="" well,="" in="" which="" case="" the="" first="" operand="" would="" be="" the="" universal="" set="" u="" and="" the="" second="" operand="" would="" be="" the="" set="" you="" want="" to="" comple-="" ment="" as="" shown="" below.="" {xlxgs="U-s" set="" complement_set="" (set="" s)="" this="" function="" is="" used="" to="" return="" the="" complement="" of="" a="" given="" set.="" by="" complement="" we="" mean="" that="" all="" bits="" in="" the="" set="" are="" flipped="" using="" the="" not="" operator.="" thus,="" the="" set="" that="" is="" returned="" contains="" all="" the="" elements="" of="" the="" universal="" set="" u="" that="" are="" not="" in="" s="" and="" contains="" none="" of="" the="" elements="" that="" are="" present="" in="" s.="" description="" 1="" describe="" how="" the="" program="" works="" with="" supporting="" pseudocode.="" description="" 2="" what="" you="" learned="" from="" the="" different="" sorting="" algorithms.under="" what="" conditions="" do="" sorts="" perorm="" well?="" under="" what="" conditions="" do="" sorts="" perform="" poorly?="" what="" conclusions="" can="" you="" make="" from="" your="" findings?="" graphs="" explaining="" the="" performance="" of="" the="" sorts="" on="" a="" variety="" of="" inputs,such="" as="" array="" sin="" reverse="" order,="" arrays="" with="" a="" small="" number="" of="" elements,="" and="" arrays="" with="" a="" large="" number="" of="" elements.="" your="" graphs="" must="" be="" produced="" using="" either="" gnuplot="" or="" matplotlib.="" you="" will="" find="" it="" helpful="" to="" write="" a="" script="" to="" handle="" the="" plotting.="" as="" always,="" awk="" will="" be="" helpful="" for="" parsing="" the="" output="" of="" your="" program.="" analysis="" of="" the="" graphs="" you="" produce.="" you="" should="" look="" carefully="" at="" any="" graphs="" that="" you="" produce.="" are="" all="" of="" the="" lines="" smooth?="" for="" example,="" in="" this="" graph="" there="" are="" some="" features="" of="" interest.="" what="" could="" be="" causing="" features="" that="" appear="" in="" your="" own="" graphs?="" here="" is="" an="" example="" graph="" produced="" by="" gnuplot="" with="" a="" different="" set="" of="" sorts="" for="" reference="" (axes="" are="">
Answered 8 days AfterJan 30, 2023

Answer To: 7 Your TaskFind out the reason that commands you to write; see whether it has spreadits roots...

Nidhi answered on Feb 07 2023
34 Votes
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here