CSE 13S Assignment 3

Algorithm 算法代写 / C语言代写

CSE 13S Assignment 3
Sorting: Putting your affairs in order
1 Introduction
Due: February 5th at 11:59 pm
Any inaccuracies in this index may be explained by the fact that it has been sorted with the help of a computer.
—Donald Knuth, Vol. III, Sorting and Searching
Putting items into a sorted order is one of the most common tasks in Computer Science. As a result, there are a myriad of library routines that will do this task for you, but that does not absolve you of the obligation of understanding how it is done. In fact, it behooves you to understand the various algorithms in order to make wise choices.
The best execution time that can be accomplished, also referred to as the lower bound, for sorting using comparisons is Ω(nlogn), where n is the number is elements to be sorted. If the universe of ele- ments to be sorted is small, then we can do better using a Count Sort or a Radix Sort both of which have a time complexity of O(n). The idea of Count Sort is to count the number of occurrences of each element in an array. For Radix Sort, a digit by digit sort is done by starting from the least significant digit to the most significant digit.
What is this O and Ω stuff? It’s how we talk about the execution time (or space used) by a program. We will discuss it in lecture and in section, and you will see it again in your Data Structures and Algorithms class, now named CSE 101.
The sorting algorithms that you are expected to implement are Shell Sort, Batcher Sort, Heap Sort, and recursive Quicksort. The purpose of this assignment is to get you fully familiarized with each sorting algorithm and for you to get a feel for computational complexity. They are well-known sorts. You can use the Python pseudocode provided to you as guides. Do not get the code for the sorts from the Internet or you will be referred to for cheating. We will be running plagiarism checkers.
2 Insertion Sort
Insertion Sort is a sorting algorithm that considers elements one at a time, placing them in their correct, ordered position. It is so simple and so ancient that we do not know who invented it. Assume an array of size n. For each k in increasing value from 1 ≤ k ≤ n (using 1-based indexing), Insertion Sort compares the k-th element with each of the preceding elements in descending order until its position is found.
© 2023 Darrell Long 1

Assume we’re sorting an array A in increasing order. We start from and check if A[k] is in the correct order by comparing it the element A[k − 1]. There are two possibilities at this point:
1. A[k] is in the right place. This means that A[k] is greater or equal to A[k − 1], and thus we can move onto sorting the next element.
2. A[k] is in the wrong place. Thus, A[k − 1] is shifted up to A[k], and the original value of A[k] is further compared to A[k − 2]. Intuitively, Insertion Sort simply shifts elements back until the element to place in sorted order is slotted in.
3
Shell Sort
Insertion Sort in Python
1 2 3 4 5 6 7 8
def insertion_sort(A: list): for i in range(1, len(A)):
j=i
temp = A[i]
while j > 0 and temp < A[j – 1]:
A[j] = A[j – 1]
j -= 1 A[j] = temp
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.
—C.A.R. Hoare
Donald L. Shell (March 1, 1924–November 2, 2015) was an American computer scientist who designed the Shell sort sorting algorithm. He earned his Ph.D. in Mathematics from the University of Cincinnati in 1959, and published the Shell Sort algorithm in the Communications of the ACM in July that same year.
Shell Sort is a variation of insertion sort, which sorts pairs of elements which are far apart from each other. The gap between the compared items being sorted is continuously reduced. Shell Sort starts with distant elements and moves out-of-place elements into position faster than a simple nearest neighbor exchange. What is the expected time complexity of Shell Sort? It depends entirely upon the gap sequence.
The following is the pseudocode for Shell Sort. The gap sequence is represented by the array gaps. You will be given a gap sequence, the Pratt sequence (2p3q also called 3-smooth), in the header file gaps.h. For each gap in the gap sequence, the function compares all the pairs in arr that are gap indices away from each other. Pairs are swapped if they are in the wrong order.
© 2023 Darrell Long 2

Shell Sort in Python
1 2 3 4 5 6 7 8 9
4 Heapsort
def shell_sort(arr): for gap in gaps:
for i in range(gap, len(arr)): j=i
temp = arr[i]
while j >= gap and temp < arr[j – gap]:
arr[j] = arr[j – gap]
j -= gap arr[j] = temp
Increasingly, people seem to misinterpret complexity as sophistication, which is baffling – the incomprehensible should cause suspicion rather than admiration.
—Niklaus Wirth
Heapsort, along with the heap data structure, was invented in 1964 by J. W. J. Williams. The heap data structure is typically implemented as a specialized binary tree. There are two kinds of heaps: max heaps and min heaps. In a max heap, any parent node must have a value that is greater than or equal to the values of its children. For a min heap, any parent node must have a value that is less than or equal to the values of its children. The heap is typically represented as an array, in which for any index k, the index of its left child is 2k and the index of its right child is 2k + 1. It’s easy to see then that the parent index of any index k should be ⌊ k2 ⌋.
Heapsort, as you may imagine, utilizes a heap to sort elements. Heapsort sorts its elements using two routines that 1) build a heap, 2) fix a heap.
1. Building a heap. The first routine is taking the array to sort and building a heap from it. This means ordering the array elements such that they obey the constraints of a max or min heap. For our purposes, the constructed heap will be a max heap. This means that the largest element, the root of the heap, is the first element of the array from which the heap is built.
© 2023 Darrell Long
3
13 58 0123
13 5 8 0 1 2 3
Figure 1: A max heap and its array representation.

2. Fixing a heap. The second routine is needed as we sort the array. The gist of Heapsort is that the largest array elements are repeatedly removed from the top of the heap and placed at the end of the sorted array, if the array is to be sorted in increasing order. After removing the largest element from the heap, the heap needs to be fixed so that it once again obeys the constraints of a heap.
In the following Python code for Heapsort, you will notice a lot of indices are shifted down by 1. Why is this? Recall how indices of children are computed. The formula of the left child of k being 2k only works assuming 1-based indexing. We, in Computer Science, especially in C, use 0-based indexing. So, we will run the algorithm assuming 1-based indexing for the Heapsort algorithm itself, subtracting 1 on each array index access to account for 0-based indexing.
Heap maintenance in Python
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
Heapsort in Python
1 2 3 4 5 6 7 8 9
10 11
© 2023 Darrell Long 4
def max_child(A: list, first: int, last: int): left = 2 * first
right = left + 1
if right <= last and A[right – 1] > A[left – 1]:
return right return left
def fix_heap(A: list, first: int, last: int): found = False
mother = first
great = max_child(A, mother , last)
while mother <= last // 2 and not found: if A[mother – 1] < A[great – 1]:
A[mother – 1], A[great – 1] = A[great – 1], A[mother – 1] mother = great
great = max_child(A, mother , last)
else:
found = True
def build_heap(A: list, first: int, last: int): for father in range(last // 2, first – 1, -1):
fix_heap(A, father , last)
def heap_sort(A: list): first = 1
last = len(A)
build_heap(A, first, last)
for leaf in range(last, first, -1):
A[first – 1], A[leaf – 1] = A[leaf – 1], A[first – 1] fix_heap(A, first , leaf – 1)

5 Quicksort
If debugging is the process of removing software bugs, then programming must be the process of putting them in.
—Edsger Dijkstra
Quicksort (sometimes called partition-exchange sort) was developed by British computer scientist C.A.R. “Tony” Hoare in 1959 and published in 1961. It is perhaps the most commonly used algorithm for sorting (by competent programmers). When implemented well, it is the fastest known algorithm that sorts using comparisons. It is usually two or three times faster than its main competitors, Merge Sort and Heapsort. It does, though, have a worst case performance of O(n2) while its competitors are strictly O(nlogn) in their worst case.
Quicksort is a divide-and-conquer algorithm. It partitions arrays into two sub-arrays by selecting an element from the array and designating it as a pivot. Elements in the array that are less than the pivot go to the left sub-array, and elements in the array that are greater than or equal to the pivot go to the right sub-array.
Note that Quicksort is an in-place algorithm, meaning it doesn’t allocate additional memory for sub- arrays to hold partitioned elements. Instead, Quicksort utilizes a subroutine called partition() that places elements less than the pivot into the left side of the array and elements greater than or equal to the pivot into the right side and returns the index that indicates the division between the partitioned parts of the array. Quicksort is then applied recursively on the partitioned parts of the array, thereby sorting each array partition containing at least one element. Like with the Heapsort algorithm, the provided Quicksort pseudocode operates on 1-based indexing, subtracting one to account for 0-based indexing whenever array elements are accessed.
Partition in Python
1 2 3 4 5 6 7 8
Recursive Quicksort in Python
1 2 3 4 5 6 7 8 9
© 2023 Darrell Long 5
def partition(A: list, lo: int, hi: int): i = lo – 1
for j in range(lo, hi):
if A[j – 1] < A[hi – 1]:
i += 1
A[i – 1], A[j – 1] = A[j – 1], A[i – 1] A[i], A[hi – 1] = A[hi – 1], A[i]
return i + 1
# A recursive helper function for Quicksort.
def quick_sorter(A: list, lo: int, hi: int): if lo < hi:
p = partition(A, lo, hi) quick_sorter(A, lo, p – 1) quick_sorter(A, p + 1, hi)
def quick_sort(A: list): quick_sorter(A, 1, len(A))

6
Batcher’s Odd-Even Merge Sort
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.
—C.A.R. Hoare
Batcher’s odd-even mergesort, or Batcher’s method, is unlike the other presented sorts in that it is actually a sorting network. What is a sorting network? Sorting networks, or comparator networks, are circuits built for the express purpose of sorting a set number of inputs. Sorting networks are built with a fixed number of wires, one for each input to sort, and are connected using comparators. Comparators compare the values traveling along the two wires they connect and swap the values if they’re out of order. Since there are a fixed number of comparators, a sorting network must necessarily sort any input using a fixed number of comparisons. Refer to Figure 2 for a diagram of a sorting network using Batcher’s method.
Sorting networks are typically limited to inputs that are powers of 2. Batcher’s method is no exception to this. To remedy this, we apply Knuth’s modification to Batcher’s method to allow it sort arbitrary-size inputs. This modification on Batcher’s method is also referred to as the Merge Exchange Sort. You will be implementing the merge exchange sort, or Batcher’s method, using the provided Python pseudocode.
Merge Exchange Sort (Batcher’s Method) in Python
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
The pseudocode for Batcher’s method can be a little mysterious, but it effectively acts as a parallel © 2023 Darrell Long 6
def comparator(A: list, x: int, y: int): if A[x] > A[y]:
A[x], A[y] = A[y], A[x]
def batcher_sort(A: list): if len(A) == 0:
return
n = len(A)
t = n.bit_length() p = 1 << (t – 1)
while p > 0:
q = 1 << (t – 1) r=0
d=p
while d > 0:
for i in range(0, n – d):
if (i & p) == r: comparator(A, i, i + d)
d=q-p q >>= 1 r=p
p >>= 1

Shell Sort. Shell Sort acts a variation of Insert Sort and first sorts pairs of elements which are far apart from each other. The distance between these pairs of elements is called a gap. Each iteration of Shell Sort decreases the gap until a gap of 1 is used.
Batcher’s method is similar, but instead of sorting pairs of elements that are a set gap apart, it k- sorts the even and odd subsequences of the array, where k is some power of 2. Given an array A where Ai denotes the i-th index of A, an even subsequence refers to the sequence of values {A0,A2,A4,…}. Similarly,anoddsubsequencereferstothesequenceofvalues{A1,A3,A5,…}. Thetopicofk-sortingis beyond the scope of this course, but all that you are required to understand is that if an array is k-sorted, then all its elements are at most k indices away from its sorted position.
Consider an array of 16 elements. Batcher’s method first 8-sorts the even and odd subsequences, then 4-sorts them, then 2-sorts them, and finally 1-sorts them, merging the sorted even and odd sequences. We will call each level of k-sorting a round. As stated previously, Batcher’s method works in parallel. By virtue of the algorithm, any indices that appear in a pairwise comparison when k-sorting a subsequence do not appear as indices in another comparison during the same round. A clever use of the bitwise AND operator, &, guarantees this property.
When computing the bitwise AND operator of two integers x and y , the resulting integer is composed of 0-bits except in the positions where both x and y have a 1-bit. As an example, let x = 10 = 10102 and y = 8 = 10002. Bitwise AND-ing x and y yields z = 8 = 10002. In the provided pseudocode, the variable p tracks the current round of k-sorting. It is always a power of 2 since it starts off as a power of 2, and is only halved in value using the right-shift operator (>>). The condition on line 20 of the pseudocode first computes the bitwise AND of i and p. This effectively partitions values of i into partitions of size p. The variable r effectively represents which partitions can be considered for comparison. Thus, (i & p) == r checks if the partition that i falls into is eligible for comparison, and if it is, to execute the comparison.
Indices are only ever compared with indices that are d indices away. Since p is a power of 2 and d is an odd multiple of p, it follows that i & p != (i + d) & p for any i. This means there is no overlap with any of the pairs of indices, which therefore means that these comparisons can be run simultaneously, or in parallel, with no ill effect. These parallel comparisons are shown clearly in Figure 2.
Although Batcher’s method can be run in parallel, your implementation of the sort will run sequen- tially, sorting the input over several rounds. For an array size of n, the initial value to k-sort with is k = ⌈log2(n)⌉. The even and odd subsequences are first k-sorted, then k2 -sorted, then k4 -sorted, and so on until they are 1-sorted. You will want to edit the provided pseudocode to print out the pairs of indices that are being compared to see what is happening.
Figure 2: Batcher’s odd-even mergesort sorting network with eight inputs. Inputs traveling along the wires are sorted as they move from left to right.
© 2023 Darrell Long 7

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:Employsallsortingalgorithms.
• -h:EnablesHeapSort.
• -b:EnablesBatcherSort.
• -s:EnablesShellSort.
• -q:EnablesQuicksort.
• -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:Printsoutprogramusage.Seereferenceprogramforexampleofwhattoprint.
It is 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.
© 2023 Darrell Long 8

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 function declarations for sets is given in the resources repository in set.h. You may not modify this file.
You are tasked with implementing the functions listed within set.h in a separate file named set.c. In the context of this assignment, a Set is nothing more than a type alias for a 32 bit integer. As you should recall from CSE 12, a bit may have one of two states, either 0 or 1. Membership of a set will be handled similarly, either an index is a member of the set, or it isn’t. Every bit within the set represents membership of a different element up until a maximum of 32 possible elements, numbered 0 through 31 inclusively.
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 in C:
& bit-wise AND | bit-wise OR
~ bit-wise NOT
^ bit-wise XOR << left shift
>> right shift
Performs the AND operation on every bit of two numbers. Performs the OR operation on every bit of two numbers.
Inverts all bits in the given number.
Performs the exclusive-OR operation on every bit of two numbers. Shifts bits in a number to the left by a specified number of bits. 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. Using these func- tions, 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 set_empty(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.
Set set_universal(void)
This function is used to return a set in which every possible member is part of the set.
Set set_insert(Set s, uint8_t x)
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 set_remove(Set s, uint8_t x)
© 2023 Darrell Long
s − x = {y|y ∈ s ∧ y ̸= x}
9

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.
bool set_member(Set s, uint8_t x)
x∈s ⇐⇒ xisamemberofsets
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 set_union(Set s, Set t)
s∪t ={x|x ∈s∨x ∈t}
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 1 in either s or t are in the new set returned by the function.
Set set_intersect(Set s, Set t)
s∩t ={x|x ∈s∧x ∈t}
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 set_difference(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 not in 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.
© 2023 Darrell Long
10
s = {x|x ∉ s} = U − s

Set set_complement(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.
9 Testing
• Youwilltesteachofthesortsspecifiedbycommand-lineoptionbysortinganarrayofpseudoran- dom numbers generated with random(). Each of your sorts should sort the same pseudorandom array. Hint: make use of srandom().
• The pseudorandom numbers generated by random() should be bit-masked to fit in 30 bits. Hint: use bit-wise AND.
• Your test harness must be able to test your sorts with array sizes up to the memory limit of the computer. That means that you will need to dynamically allocate the array.
• Your program should have no memory leaks. Make sure you free() before exiting. valgrind should pass cleanly with any combination of the specified command-line options.
• Youralgorithmsmustcorrectlysort.Anyalgorithmthatdoesnotsortcorrectlywillreceiveazero.
A large part of this assignment is understanding and comparing the performance of various sorting algorithms. You essentially conducting an experiment. As stated in §7, you must collect the following statistics on each algorithm:
• Thesizeofthearray,
• Thenumberofmovesrequired(eachtimeyoutransferanelementinthearray,thatcounts),and • Thenumberofcomparisonsrequired(comparisonsonlycountforelements,notforlogic).
10 Output
Books are not made to be believed, but to be subjected to inquiry. When we consider a book, we mustn’t ask ourselves what it says but what it means.
The output your test harness produces must be formatted like in the following examples:
© 2023 Darrell Long 11
—Umberto Eco

-q -n 1000 -p 0 1000 elements , -h -n 15 -p 0
$ ./sorting
Quick Sort ,
$ ./sorting
Heap Sort , 15 elements , 144
18642 moves , 10531 compares moves , 70 compares
moves , 59 compares
$ ./ sorting Shell Sort ,
-a -n 15
15 34732749 134750049 954916333 Batcher Sort , 34732749 134750049 954916333 Sort , 15 34732749 134750049 954916333
Quick Sort , 15
34732749 42067670
134750049 182960600 954916333 966879077
Heap
994582085 moves , 70 compares
elements , 90 42067670 182960600 966879077 elements , 42067670 182960600 966879077
elements , 144 42067670 182960600 966879077
54998264 538219612 989854347 moves , 59
54998264 538219612 989854347
102476060 629948093 994582085
compares 102476060
629948093
104268822
783585680 1072766566
104268822
783585680 1072766566
104268822
783585680 1072766566
104268822
783585680 1072766566
15
90
elements , 135
54998264 538219612 989854347
moves , 51 54998264 538219612 989854347
102476060 629948093 994582085
compares 102476060
629948093 994582085
For each sort that was specified, print its name, the statistics for the run, then the specified number of array elements to print. The array elements should be printed out in a table with 5 columns. Each array element should be printed with a width of 13. You should make use of the following printf() statement:
1 printf(“%13” PRIu32); // Include for PRIu32.
11 Statistics
There are three types of lies—lies, damn lies, and statistics.
—Benjamin Disraeli
To facilitate the gathering of statistics, you will be given, and must use, a small statistics module. The module itself revolves around the following struct:
1 2 3 4
The module also includes functions to compare, swap, and move elements. int cmp(Stats *stats, uint32_t x, uint32_t y)
Compares x and y and increments the comparisons field in stats. Returns -1 if x is less than y, 0 if x is equal to y, and 1 if x is greater than y.
© 2023 Darrell Long 12
typedef struct { uint64_t moves; uint64_t comparisons;
} Stats;

uint32_t move(Stats *stats, uint32_t x)
“Moves” x by incrementing the moves field in stats and returning x. This is intended for use in Insertion Sort and Shell Sort, where array elements aren’t swapped, but instead moved and stored in a temporary variable.
void swap(Stats *stats, uint32_t *x, uint32_t *y)
Swaps the elements pointed to by pointers x and y, incrementing the moves field in stats by 3 to reflect
a swap using a temporary variable.
void reset(Stats *stats)
Resets stats, setting the moves field and comparisons field to 0. It is possible that you don’t end up
using this specific function, depending on your usage of the Stats struct. 12 Deliverables
Dr. Long, put down the Rilke and step away from the computer.
You will need to turn in the following source code and header files: 1. Yourprogrammusthavethefollowingsourceandheaderfiles:
• batcher.cimplementsBatcherSort.
• batcher.hspecifiestheinterfacetobatcher.c.
• shell.cimplementsShellSort.
• shell.hspecifiestheinterfacetoshell.c.
• gaps.hprovidesagapsequencetobeusedbyShellsort.
• heap.cimplementsHeapSort.
• heap.hspecifiestheinterfacetoheap.c.
• quick.cimplementsrecursiveQuicksort.
• quick.hspecifiestheinterfacetoquick.c.
• set.cimplementsbit-wiseSetoperations.
• set.hspecifiestheinterfacetoset.c.
• stats.cimplementsthestatisticsmodule.
• stats.hspecifiestheinterfacetothestatisticsmodule.
• sorting.ccontainsmain()andmaycontainanyotherfunctionsnecessarytocompletethe assignment.
© 2023 Darrell Long 13
—Michael Olson

You can have other source and header files, but do not try to be overly clever. The header files for each of the sorts are provided to you and may not be modified. Each sort function takes a pointer to a Stats struct, the array of uint32_ts to sort as the first parameter, and the length of the array as the second parameter. You will also need to turn in the following:
1. Makefile:
• CC = clangmustbespecified.
• CFLAGS = -Wall -Wextra -Werror -Wpedanticmustbespecified.
• makemustbuildthesortingexecutable,asshouldmake allandmake sorting. • make cleanmustremoveallfilesthatarecompilergenerated.
• make formatshouldformatallyoursourcecode,includingtheheaderfiles.
2. README.md: This must use proper Markdown syntax. It must describe how to use your program and Makefile. It should also list and explain any command-line options that your program ac- cepts. Any false positives reported by scan-build should be documented and explained here as well. Note down any known bugs or errors in this file as well for the graders.
3. DESIGN.pdf: This document must be a proper PDF. This design document must describe your design and design process for your program with enough detail such that a sufficiently knowl- edgeable programmer would be able to replicate your implementation. This does not mean copy- ing your entire program in verbatim. You should instead describe how your program works with supporting pseudocode.
4. WRITEUP.pdf:ThisdocumentmustbeaPDF.Thewriteupmustincludethefollowing:
• Whatyoulearnedfromthedifferentsortingalgorithms.Underwhatconditionsdosortsper- form well? Under what conditions do sorts perform poorly? What conclusions can you make from your findings?
• Graphsexplainingtheperformanceofthesortsonavarietyofinputs,suchasarraysinreverse 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. Here is an example graph produced by gnuplot with a different set of sorts for reference (axes are log-scaled):
© 2023 Darrell Long 14

1×108 1×107 1×106
100000
10000
1000
100
10
Heap Sort
Insertion Sort
Quick Sort
Shell Sort
Moves Performed
14
Supplemental Readings
• TheCProgrammingLanguagebyKernighan&Ritchie
– Chapter1§1.10
– Chapter3§3.5
– Chapter4§4.10–4.11
– Chapter5§5.1–5.3&5.10
• CinaNutshellbyT.Crawford&P.Prinz.
– Chapter6–Example6.5
– Chapter7–RecursiveFunctions
– Chapter8–ArraysasArgumentsofFunctions – Chapter9–PointerstoArrays
10 100
1000
10000
Elements
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?
13 Submission
Refer back assignment 0 for the instructions on how to properly submit your assignment through git. Remember: add, commit, and push!
Your assignment is turned in only after you have pushed and submitted the commit ID you want graded on Canvas. “I forgot to push” and “I forgot to submit my commit ID” are not valid excuses. It is highly recommended to commit and push your changes often.
© 2023 Darrell Long 15
Moves

© 2023 Darrell Long
16
Code Monkey like Fritos
Code Monkey like Tab and Mountain Dew Code Monkey very simple man
With big warm fuzzy secret heart: Code Monkey like you