Homework 06: Sorting Lists

The goal of this homework assignment is to allow you to explore building linked lists and sorting them using a variety of algorithms such as selection sort, merge sort, and quick sort and then utilizing these data structures and algorithms to implement a version of the sort utility called lsort.

In high-level languages such as Python, we have a built-in implementation of sorting which work on lists:

# Define a list
>>> numbers = [5, 4, 7, 0, 1]

# Sort list (into new list)
>>> sorted(numbers)
[0, 1, 4, 5, 7]

>>> numbers
[5, 4, 7, 0, 1]

# Sort list (in-place)
>>> numbers.sort()
>>> numbers
[0, 1, 4, 5, 7]

The C standard library provides qsort, but it only operates on arrays. For this assignment, you are to implement the following sorting algorithms to operate on singly linked lists.

  1. selection_sort: This uses selection sort to order the values in a singly linked list.

  2. merge_sort: This uses merge sort to order the values in a singly linked list recursively.

  3. quick_sort: This uses qsort to order the values in a singly linked list.

For this assignment, you are to do your work in the homework06 folder of your assignments GitHub repository and push your work by noon Wednesday, October 4.

Activity 0: Preparation

Before starting this homework assignment, you should first perform a git pull to retrieve any changes in your remote GitHub repository:

$ cd path/to/repository                   # Go to assignments repository

$ git switch master                       # Make sure we are in master branch

$ git pull --rebase                       # Get any remote changes not present locally

Next, create a new branch for this assignment:

$ git checkout -b homework06              # Create homework06 branch and check it out

Task 1: Skeleton Code

To help you get started, the instructor has provided you with the following skeleton code:

# Go to assignments repository
$ cd path/to/assignments/repository

# -----------------------------------------------------
# MAKE SURE YOU ARE NOT INSIDE THE homework06 DIRECTORY
# -----------------------------------------------------
# MAKE SURE YOU ARE AT THE TOP-LEVEL DIRECTORY
# -----------------------------------------------------

# Download skeleton code tarball
$ curl -LO https://www3.nd.edu/~pbui/teaching/cse.20312.fa23/static/tar/homework06.tar.gz

# Extract skeleton code tarball
$ tar xzvf homework06.tar.gz

Once downloaded and extracted, you should see the following files in your homework06 directory:

homework06
    \_ Makefile                 # This is the Makefile for building all the project artifacts
    \_ bin                      # This contains the project binary executables and test scripts
        \_ benchmark.py         # This is the Python script for benchmarking the lsort program
        \_ test_list.sh         # This is the shell script for testing the List library
        \_ test_lsort.sh        # This is the shell script for testing the lsort utility
        \_ test_merge.sh        # This is the shell script for testing the MergeSort library
        \_ test_node.sh         # This is the shell script for testing the Node library
        \_ test_quick.sh        # This is the shell script for testing the QuickSort library
        \_ test_selection.sh    # This is the shell script for testing the SelectionSort library
    \_ include                  # This contains the project header files
        \_ ds                   # This contains the project data structure header files
            \_ list.h           # This is the C header file for the List library
            \_ node.h           # This is the C header file for the Node library
            \_ sorts.h          # This is the C header file for the Sorting libraries
    \_ lib                      # This contains the project library files
    \_ src                      # This contains the project source code
        \_ list.c               # This is the C source code for the List library
        \_ lsort.c              # This is the C source code for the lsort utility
        \_ merge_sort.c         # This is the C source code for the MergeSort library
        \_ node.c               # This is the C source code for the Node library
        \_ quick_sort.c         # This is the C source code for the QuickSort library
        \_ selection_sort.c     # This is the C source code for the SelectionSort library
    \_ tests                    # This contains the project unit tests
        \_ unit_list.c          # This is the unit test for the List library
        \_ unit_merge.c         # This is the unit test for the MergeSort library
        \_ unit_node.c          # This is the unit test for the Node library
        \_ unit_quick.c         # This is the unit test for the QuickSort library
        \_ unit_selection.c     # This is the unit test for the SelectionSort library

Task 2: Initial Import

Now that the files are extracted into the homework06 folder, you can commit them to your git repository:

# Go into homework06 folder
$ cd homework06

# Add and commit initial skeleton files
$ git add Makefile                            # Mark changes for commit
$ git add bin/*.sh bin/*.py                   # Mark changes for commit
$ git add include/ds/*.h                      # Mark changes for commit
$ git add lib/.gitkeep                        # Mark changes for commit
$ git add src/*.c                             # Mark changes for commit
$ git add tests/*.c                           # Mark changes for commit
$ git commit -m "Homework 06: Initial Import" # Record changes

The details on what you need to implement are described in the following sections.

Task 3: Makefile

The Makefile contains all the rules or recipes for building the project artifacts (e.g. lsort, libds.a, unit_list, unit_merge, unit_node, unit_quick, unit_selection, etc.):

CC=       gcc
CFLAGS=   -Wall -std=gnu99 -g -Iinclude
AR=       ar
ARFLAGS=  rcs
LD=       gcc
LDFLAGS=  -Llib

all:    bin/lsort

test:
      @$(MAKE) -sk test-all

test-all:   test-node test-list test-selection test-merge test-quick test-lsort

# TODO: Pattern rule for object files

# TODO: Rule for lib/libds.a

# TODO: Rule for bin/lsort

bin/unit_node:    tests/unit_node.o lib/libds.a
      $(LD) $(LDFLAGS) -o $@ $^

bin/unit_list:    tests/unit_list.o lib/libds.a
      $(LD) $(LDFLAGS) -o $@ $^

bin/unit_selection: tests/unit_selection.o lib/libds.a
      $(LD) $(LDFLAGS) -o $@ $^

bin/unit_merge:   tests/unit_merge.o lib/libds.a
      $(LD) $(LDFLAGS) -o $@ $^

bin/unit_quick:   tests/unit_quick.o lib/libds.a
      $(LD) $(LDFLAGS) -o $@ $^

test-node:    bin/unit_node
      bin/test_node.sh

test-list:    bin/unit_list
      bin/test_list.sh

test-selection:   bin/unit_selection
      bin/test_selection.sh

test-merge:   bin/unit_merge
      bin/test_merge.sh

test-quick:   bin/unit_quick
      bin/test_quick.sh

test-lsort:   bin/lsort
      bin/test_lsort.sh

clean:
      rm -f bin/lsort bin/unit_* lib/*.a src/*.o tests/*.o

For this task, you will need to add rules for building the static library lib/libds.a and the program bin/lsort. Be sure to have a recipe for any intermediate object files that libraries require as shown in the DAG below:

Makefile Variables

You must use the CC, CFLAGS, LD, LDFLAGS, AR, and ARFLAGS variables when appropriate in your rules. You should also consider using automatic variables such as $@ and $< as well.

Once you have a working Makefile, you should be able to run the following commands:

# Build all TARGETS
$ make
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/lsort.o src/lsort.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/node.o src/node.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/list.o src/list.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/selection_sort.o src/selection_sort.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/merge_sort.o src/merge_sort.c
gcc -Wall -std=gnu99 -g -Iinclude -c -o src/quick_sort.o src/quick_sort.c
ar rcs lib/libds.a src/node.o src/list.o src/selection_sort.o src/merge_sort.o src/quick_sort.o
gcc -Llib -o bin/lsort src/lsort.o lib/libds.a

# Run all tests
$ make test
Testing node...
...

# Remove generated artifacts
$ make clean
rm -f bin/lsort bin/unit_* lib/*.a src/*.o tests/*.o

Note: The tests will fail if you haven't implemented Node, List, or sorting libraries, or the lsort program.

Warnings

You must include the -Wall flag in your CFLAGS when you compile. This also means that your code must compile without any warnings, otherwise points will be deducted.

After completing the Makefile and verifying that you can produce all the specified artifacts, you may begin implementing the data structures and applications for this assignment.

Activity 1: Node Library (1 Point)

For the first activity, you are to implement a Node structure to be used in a singly linked list. Each Node structure will have the following attributes:

  1. data: This is a pointer to a string allocated on the heap.
  2. next: This is a pointer to the next Node struct in the sequence.

Task 1: include/ds/node.h

The include/ds/node.h file is the header file for the Node structure, which contains the following structs and function prototypes:

/* node.h: Node Structure */

#pragma once

#include <stdio.h>
#include <stdlib.h>

/* Structure */

typedef struct Node Node;
struct Node {
    char *data;
    Node *next;
};

/* Type Definitions */

typedef int (*Comparison)(const void *, const void *);

/* Functions */

Node *  node_create(char *data, Node *next);
void    node_delete(Node *n);

int node_compare_as_strings(const void *a, const void *b);
int node_compare_as_numbers(const void *a, const void *b);

Other programs will #include this file in order to use the functions we will be implementing in this library.

Note: Comparison is a type definition for functions such as node_compare_as_strings and node_compare_as_numbers.

Note: For this task, you do not need to modify this file. Instead, you should review it and ensure you understand the provided code.

Task 2: src/node.c

The src/node.c file contains the C implementation for the Node structure. For this task, you will need to implement the following functions:

  1. Node* node_create(char *data, Node *next)

    This function allocates a new Node struct and initializes its internal attributes: data and next.

    Hint: Use malloc, calloc, or strdup to allocate data on the heap.

  2. void node_delete(Node *n)

    This function deallocates the given Node struct along with its internal data string.

    Hint: Use free to release data allocated on the heap.

  3. int node_compare_as_strings(const void *a, const void *b)

    This function compares two Node structures by treating their data attributes as strings.

    Hint: Use strcmp to compare strings.

    Remember that the sorting algorithms will pass you references to each element they are sorting. Therefore, if each element is a Node *, then a and b are actually Node **.

  4. int node_compare_as_numbers(const void *a, const void *b)

    This function compares two Node structures by treating their data attributes as integers.

    Hint: Use atoi to convert a string to an integer.

    Remember that a Comparison function should return 0 if the elements are equal, a negative if a < b, and a positive if a > b.

    Therefore, once you have integers, you can simply do the equivalent of a - b to perform the comparison.

Task 3: Testing

As you implement the functions in src/node.c, you should use bin/test_node.sh to test each function:

# Build unit-test
$ make bin/unit_node
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_node.o tests/unit_node.c
gcc -Llib -o bin/unit_node tests/unit_node.o lib/libds.a

# Run test script manually
$ ./bin/test_node.sh
Testing node...
 node_create                              ... Success
 node_delete                              ... Success
 node_compare_as_strings                  ... Success
 node_compare_as_numbers                  ... Success

   Score 1.00 / 1.00
  Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test-node
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_node command directly:

# Display usage message
$ ./bin/unit_node
Usage: ./bin/unit_node NUMBER

Where NUMBER is right of the following:
      0  Test node_create
      1  Test node_delete
      2  Test node_compare_as_strings
      3  Test node_compare_as_numbers

# Run test for node_create
$ ./bin/unit_node 0

# Run test for node_create using GDB
$ gdb ./bin/unit_node
...
(gdb) run 0

# Run test for node_create using Valgrind
$ valgrind --leak-check=full ./bin/unit_node 0

Of course, you are free to create your own test programs to debug and test your Node library.

Iterative Development

You should practice iterative development. That is, rather than writing a bunch of code and then debugging it all at once, you should concentrate on one function at a time and then test that one thing at a time. The provided unit tests allow you to check on the correctness of the individual functions without implementing everything at once. Take advantage of this and build one thing at a time.

Activity 2: List Library (4 Points)

For the second activity, you are to complete the List structure that implements a [singly liked list] with a tail pointer.

As can seen, each List structure has the following attributes:

  1. head: This is a pointer to the first Node struct in the sequence.
  2. tail: This is a pointer to the last Node struct in the sequence.
  3. size: This is the number of Node structures in the sequence.

Task 1: include/ds/list.h

The include/ds/list.h file is the header file for the List structure, which contains the following structs and function prototypes:

/* list.h: List Structure */

#pragma once

#include "node.h"

#include <stdio.h>
#include <stdlib.h>

/* Structure */

typedef struct {
    Node  *head;
    Node  *tail;
    size_t size;
} List;

/* Functions */

List *  list_create();
void    list_delete(List *l);

void    list_append(List *l, char *s);
void    list_dump(List *l, FILE *fs);

void    list_split(Node *n, Node **left, Node **right);
Node *  list_merge(Node *left, Node *right, Comparison cmp);

Node**  list_nodes(List *l);
void    list_update(List *l, Node **a);

Note: For this task, you do not need to modify this file. Instead, you should review it and ensure you understand the provided code.

Task 2: src/list.c

The src/list.c file contains the C implementation for the List structure. For this task, you will need to implement the following functions:

  1. List* list_create()

    This function allocates a new ListSet struct and initializes its internal attributes: head, tail, and size.

    Hint: Use malloc or calloc to allocate data on the heap.

  2. void list_delete(List *l)

    This function deallocates all the internal Node structures in the List structure, and then the List struct itself.

    Hint: Use node_delete and free to deallocate the appropriate objects from the heap.

  3. void list_append(List *l, char *s)

    This function creates a new Node struct with the given string s and adds it to the back of the internal singly linked list (e.g. l.append(s) in Python).

    Hint: Use node_create and make sure you update the head, tail, and size attributes of the List struct appropriately.

  4. void list_dump(List *l, FILE *fs)

    This function prints every value in the List struct to the given stream (one value per line).

  5. void list_split(Node *n, Node **left, Node **right)

    This function splits the singly linked list starting at n into two relatively equally sized sublists: left and right. After this function, left will point to the first node in the left sublist, and right will point to the first node in the right sublist.

    Hint: Use the slow and fast pointer technique to find the middle of the singly linked list.

    To terminate the left sublist, consider adding a tail pointer in addition to a slow and fast pointer and setting tail->next to NULL.

  6. Node * list_merge(Node *left, Node *right, Comparison cmp)

    This function merges the left and right singly linked lists into one ordered singly linked list and returns the pointer to the first Node in the new sequence. To compare Node structures, it uses the provided cmp Comparison function.

    Hint: First determine which Node from either the left or right is the head of the new singly linked list. Next, connect the smallest element from either the left or right subsequences to the tail of the new singly linked list until either subsequence is exhausted. Finally, connect the remaining subsequence to the tail of the new singly linked list.

  7. Node ** list_nodes(List *l)

    This function returns an array of pointers to the Node structures in the given List struct.

    Hint: Use malloc or calloc to allocate data on the heap.

  8. void list_update(List *l, Node **a)

    This function updates the internal Node structures in the List structure with the ordering in the given array of Node structs.

    Hint: Update the next pointer of each pair of Node structs in the array and then update the head and tail of the List. Be sure to properly terminate the sequence.

Task 3: Testing

As you implement the functions in src/list.c, you should use bin/test_list.sh to test each function:

# Build unit-test
$ make bin/unit_list
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_list.o tests/unit_list.c
gcc -Llib -o bin/unit_list tests/unit_list.o lib/libds.a

# Run test script manually
$ ./bin/test_list.sh
Testing list...
 list_create                              ... Success
 list_delete                              ... Success
 list_append                              ... Success
 list_dump                                ... Success
 list_split                               ... Success
 list_merge                               ... Success
 list_nodes                               ... Success
 list_update                              ... Success

   Score 3.00 / 3.00
  Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test-list
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_list command directly:

# Display usage message
$ ./bin/unit_list
Usage: ./bin/unit_list NUMBER

Where NUMBER is right of the following:
    0  Test list_create
    1  Test list_delete
    2  Test list_append
    3  Test list_dump
    4  Test list_split
    5  Test list_merge
    6  Test list_nodes
    7  Test list_update

# Run test for list_create
$ ./bin/unit_list 0

# Run test for list_create using GDB
$ gdb ./bin/unit_list
...
(gdb) run 0

# Run test for list_create using Valgrind
$ valgrind --leak-check=full ./bin/unit_list 0

Of course, you are free to create your own test programs to debug and test your List library.

Activity 3: Selection Sort (1 Point)

For this activity, you are to implement selection sort.

As discussed in class, selection sort involves finding the minimum value in a subsequence and swapping it with the current value if necessary.

Task 1: include/ds/sorts.h

The include/ds/sorts.h file is the header file for all the sorting algorithms, which contains the following function prototypes:

/* sorts.h: Sorting Algorithms */

#pragma once

#include "ds/list.h"

/* Functions */

void  selection_sort(List *l, Comparison cmp);
void  merge_sort(List *l, Comparison cmp);
void  quick_sort(List *l, Comparison cmp);

Note: For this task, you do not need to modify this file. Instead, you should review it and ensure you understand the provided code.

Task 2: src/selection_sort.c

The src/selection_sort.c file contains the C implementation for the selection sort algorithm. For this task, you will need to implement the following functions:

  1. void selection_sort(List *l, Comparison cmp)

    This function performs selection sort on the given List and orders values using the specified Comparison function.

    Hint: You can just swap the data attributes of the current and minimum Nodes. You don't have to swap the actual Node structs.

Task 3: Testing

As you implement the functions in src/selection_sort.c, you should use bin/test_selection.sh to test each function:

# Build unit-test
$ make bin/unit_selection
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_selection.o tests/unit_selection.c
gcc -Llib -o bin/unit_selection tests/unit_selection.o lib/libds.a

# Run test script manually
$ ./bin/test_selection.sh
Testing selection...
 selection_sort_strings                   ... Success
 selection_sort_numbers                   ... Success

  Score 1.00 / 1.00
 Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test-selection
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_selection command directly:

# Display usage message
$ ./bin/unit_selection
Usage: ./bin/unit_selection NUMBER

Where NUMBER is right of the following:

    0  Test selection_sort_strings
    1  Test selection_sort_numbers

# Run test for selection_sort
$ ./bin/unit_selection 0

# Run test for selection_sort using GDB
$ gdb ./bin/unit_selection
...
(gdb) run 0

# Run test for selection_sort using Valgrind
$ valgrind --leak-check=full ./bin/unit_selection 0

Of course, you are free to create your own test programs to debug and test your selection sort implementation.

Activity 4: Merge Sort (3 Points)

For this activity, you are to use divide-and-conquer to recursively implement merge sort.

As discussed in class, merge sort uses divide-and-conquer:

  1. Divide: Split the List in half.
  2. Conquer: Recursively sort the left and right subsequences.
  3. Combine: Merge the sorted subsequences.

Task 1: src/merge_sort.c

The src/merge_sort.c file contains the C implementation for the merge sort algorithm. For this task, you will need to implement the following functions:

  1. void merge_sort(List *l, Comparison cmp)

    This function performs merge sort on the given List and orders values using the specified Comparison function.

    Hint: You can update the head with merge_sort_r and then update the tail once the the List is sorted.

  2. Node * merge_sort_r(Node *n, Comparison cmp)

    This helper function uses divide-and-conquer to recursively perform merge sort on the given sequence that begins with n and returns a pointer to the the first Node struct in the sorted sequence.

    Hint: Consider using list_split and list_merge.

Task 2: Testing

As you implement the functions in src/merge_sort.c, you should use bin/test_merge.sh to test each function:

# Build unit-test
$ make bin/unit_merge
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_merge.o tests/unit_merge.c
gcc -Llib -o bin/unit_merge tests/unit_merge.o lib/libds.a

# Run test script manually
$ ./bin/test_merge.sh
Testing merge...
 merge_sort_strings                   ... Success
 merge_sort_numbers                   ... Success

  Score 3.00 / 3.00
 Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test-merge
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_merge command directly:

# Display usage message
$ ./bin/unit_merge
Usage: ./bin/unit_merge NUMBER

Where NUMBER is right of the following:

    0  Test merge_sort_strings
    1  Test merge_sort_numbers

# Run test for merge_sort
$ ./bin/unit_merge 0

# Run test for merge_sort using GDB
$ gdb ./bin/unit_merge
...
(gdb) run 0

# Run test for merge_sort using Valgrind
$ valgrind --leak-check=full ./bin/unit_merge 0

Of course, you are free to create your own test programs to debug and test your merge sort implementation.

Activity 5: Quick Sort (1 Point)

For this activity, you are to use qsort to implement quick sort. To do this, you will convert the singly linked list in the List structure into an array, perform qsort on the array, and then update the original List structure.

Task 1: src/quick_sort.c

The src/quick_sort.c file contains the C implementation for the quick sort algorithm. For this task, you will need to implement the following functions:

  1. void quick_sort(List *l, Comparison cmp)

    This function performs quick sort on the given List and orders values using the specified Comparison function.

    Hint: Consider using list_nodes and list_update.

Task 2: Testing

As you implement the functions in src/quick_sort.c, you should use bin/test_quick.sh to test each function:

# Build unit-test
$ make bin/unit_quick
gcc -Wall -std=gnu99 -g -Iinclude -c -o tests/unit_quick.o tests/unit_quick.c
gcc -Llib -o bin/unit_quick tests/unit_quick.o lib/libds.a

# Run test script manually
$ ./bin/test_quick.sh
Testing quick...
 quick_sort_strings                   ... Success
 quick_sort_numbers                   ... Success

  Score 1.00 / 1.00
 Status Success

Alternatively, you can both build the artifacts and run the test script by doing the following:

# Build and run test scripts
$ make test-quick
...

If one of the functions fails, and you need to debug the unit tests, you can run the bin/unit_quick command directly:

# Display usage message
$ ./bin/unit_quick
Usage: ./bin/unit_quick NUMBER

Where NUMBER is right of the following:

    0  Test quick_sort_strings
    1  Test quick_sort_numbers

# Run test for quick_sort
$ ./bin/unit_quick 0

# Run test for quick_sort using GDB
$ gdb ./bin/unit_quick
...
(gdb) run 0

# Run test for quick_sort using Valgrind
$ valgrind --leak-check=full ./bin/unit_quick 0

Of course, you are free to create your own test programs to debug and test your quick sort implementation.

Activity 6: List Sort (2 Points)

For the last activity, you are to use your List and sorting algorithms library to implement a version of the traditional Unix utility called bin/lsort.

# Use selection sort to order input as strings
$ seq 1 10 | ./bin/lsort
1
10
2
3
4
5
6
7
8
9

# Use quick sort to order input as numbers
$ seq 1 10 | ./bin/lsort -q -n
1
2
3
4
5
6
7
8
9
10

The bin/lsort program should support the following command line options:

  1. -m: Use merge sort.
  2. -q: Use quick sort.
  3. -n: Compare each line as numbers.

By default, bin/lsort uses selection sort and compares each line as strings.

Memory Management

In addition to meeting the functional requirements of the assignment (as described above), your program must not exhibit any memory leaks or invalid memory accesses as would be detected by Valgrind.

Be sure to free any memory that has been allocated on the heap and to initialize any allocate memory appropriately.

Task 1: src/lsort.c

The src/lsort.c file contains the C implementation of the bin/lsort program described above. You will need to implement the following functions:

  1. int main(int argc, char *argv[])

    This function should do the following:

    1. Parse the command line options.
    2. Read each line from stdin into a List.
    3. Sort the List using the appropriate sorting algorithm.
    4. Dump the contents of the List.

Hint: Take advantage of the Function and Comparison type definitions to treat functions as pointers that can be assigned to variables:

// Assign functions as variables
Function    sort = selection_sort;
Comparison  cmp  = node_compare_as_strings;

...

// Use function variables
sort(l, cmp);

Task 2: Testing

As you implement src/lsort.c, you can test it by running the test-lsort target:

# Build artifact and run test
$ make test-lsort
bin/test_lsort.sh
Testing lsort ...
  Selection Sort - Strings (output)        ... Success
  Selection Sort - Strings (valgrind)      ... Success
  Selection Sort - Numbers (output)        ... Success
  Selection Sort - Numbers (valgrind)      ... Success
  Merge Sort - Strings (output)            ... Success
  Merge Sort - Strings (valgrind)          ... Success
  Merge Sort - Numbers (output)            ... Success
  Merge Sort - Numbers (valgrind)          ... Success
  Quick Sort - Strings (output)            ... Success
  Quick Sort - Strings (valgrind)          ... Success
  Quick Sort - Numbers (output)            ... Success
  Quick Sort - Numbers (valgrind)          ... Success

   Score 2.00 / 2.00
  Status Success

Activity 7: Quiz (2 Points)

Once you have completed all the activities above, you are to complete the following reflection quiz:

As with Reading 01, you will need to store your answers in a homework06/answers.json file. You can use the form above to generate the contents of this file, or you can write the JSON by hand.

To check your quiz directly, you can use the check.py script:

$ ../.scripts/check.py
Checking homework06 quiz ...
      Q1 0.40
      Q2 0.40
      Q3 0.30
      Q4 0.30
      Q5 0.20
      Q6 0.10
      Q7 0.30

   Score 2.00 / 2.00
  Status Success

Leet Point (1 Extra Credit Point)

For extra credit, you are to solve the following LeetCode problem in C.

2037. Minimum Number of Moves to Seat Everyone

To receive credit, you must pass on LeetCode and achieve an Accepted submission.

Verification

To get credit for this Leet Point, show your solution and the LeetCode acceptance page to a TA to verify (or attached a screenshot with both to your Pull Request). You have up until two days after this assignment is due to verify your Leet Point.

Self-Service Extension

Remember that you can always forgo this Leet Point for two extra days to do the homework. That is, if you need an extension, you can simply skip the Leet Point and you will automatically have until Friday to complete the assignment for full credit.

Just leave a note on your Pull Request of your intentions.

Submission

To submit your assignment, please commit your work to the homework06 folder of your homework06 branch in your assignments GitHub repository:

#-----------------------------------------------------------------------
# Make sure you have already completed Activity 0: Preparation
#-----------------------------------------------------------------------
...
$ git add Makefile                            # Mark changes for commit
$ git commit -m "Homework 06: Activity 0"     # Record changes
...
$ git add src/node.c                          # Mark changes for commit
$ git commit -m "Homework 06: Activity 1"     # Record changes
...
$ git add src/list.c                          # Mark changes for commit
$ git commit -m "Homework 06: Activity 2"     # Record changes
...
$ git add src/selection_sort.c                # Mark changes for commit
$ git commit -m "Homework 06: Activity 3"     # Record changes
...
$ git add src/merge_sort.c                    # Mark changes for commit
$ git commit -m "Homework 06: Activity 4"     # Record changes
...
$ git add src/quick_sort.c                    # Mark changes for commit
$ git commit -m "Homework 06: Activity 5"     # Record changes
...
$ git add src/lsort.c                         # Mark changes for commit
$ git commit -m "Homework 06: Activity 6"     # Record changes
...
$ git add answers.json                        # Mark changes for commit
$ git commit -m "Homework 06: Activity 7"     # Record changes
...

$ git push -u origin homework06               # Push branch to GitHub

Pull Request

Remember to create a Pull Request and assign the appropriate TA from the Reading 06 TA List.

DO NOT MERGE your own Pull Request. The TAs use open Pull Requests to keep track of which assignments to grade. Closing them yourself will cause a delay in grading and confuse the TAs.