1 Introduction

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 Ω (n logn), 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 Sortboth 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 s k s 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.

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

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 (2p 3q 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.

4 Heapsort

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 l 」.

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.

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.

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(n logn) 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.

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.

The pseudocode for Batcher’s method can be a little mysterious, but it effectively acts as a parallel

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, an odd subsequence refers to the sequence of values {A1 , A3 , A5 , . . . }. The topic of k-sorting is 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)1. The even and odd subsequences are first k-sorted, then -sorted, then -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.

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.

• -s : 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.

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.

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:

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)

s - x = {yly e s A y \= 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.

bool set_member(Set s, uint8_t x)

x e s e→ x is a member of set s

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 u t = {xlx e s v x e 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 n t = {xlx e s A x e 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&n