CS253 HW1: Counting Sort                

Changes                

The C int array used to store the counts must have exactly 100 entries.                 

Description                

For this assignment, you will write a C++ program called hw1 that will read integers in the range 0…99 from standard input, and perform a counting sort on the integers. It will display the sorted integers in two ways: firstly as integers and counts, secondly as repeated integers.                 

Counting sort                

Start with an array of zeroes. It contains counts, representing how many times each integer has been seen:                 

Of course, this array can only handles values 0…9.                 

We read the value 5. Increment location 5 from 0 to 1:                 

Then, we read 6, another 5, a 2, and yet another 5, incrementing as we go:                 

Now, we scan the array, ignoring the 0 counts. We see 1 instance of 2, 3 instances of 5, and 1 instance of 6. We could write that out like this:

    2x1 5x3 6x1

or, equivalently:

    2,5,5,5,6

Look! The integers are sorted!                 

Sample Run                

Here is a sample run, where % is my prompt.                 

% cat CMakeLists.txt
cmake_minimum_required(VERSION 3.11)
project(hw1)

# Are we in the wrong directory?
if (CMAKE_SOURCE_DIR MATCHES "[Hh][Ww]([0-9])$"
   AND NOT PROJECT_NAME MATCHES "${CMAKE_MATCH_1}$")
    message(FATAL_ERROR "Building ${PROJECT_NAME} in ${CMAKE_SOURCE_DIR}")
endif()

# Using -Wall is required:
add_compile_options(-Wall)

# These compile flags are highly recommended, but not required:
add_compile_options(-Wextra -Wpedantic)

# Optional super-strict mode:
add_compile_options(-fmessage-length=80 -fno-diagnostics-show-option
    -fstack-protector-all -g -O3 -std=c++17 -Walloc-zero -Walloca
    -Wctor-dtor-privacy -Wduplicated-cond -Wduplicated-branches
    -Werror -Wextra-semi -Wfatal-errors -Winit-self -Wlogical-op
    -Wold-style-cast -Wshadow -Wunused-const-variable=1
    -Wzero-as-null-pointer-constant)

# add_compile_options must be BEFORE add_executable.

# Create the executable from the source file main.cc:
add_executable(${PROJECT_NAME} main.cc)

# Create a tar file every time:
add_custom_target(${PROJECT_NAME}.tar ALL COMMAND
    tar -cf ${PROJECT_NAME}.tar *.cc CMakeLists.txt)
% cmake . && make
… cmake output appears here …
… make output appears here …
% cat data
42 13
99 013 00013

4
42 0 42 42 42 42

% ./hw1 <data
0x1 4x1 13x3 42x6 99x1
0,4,13,13,13,42,42,42,42,42,42,99
% cat data | ./hw1
0x1 4x1 13x3 42x6 99x1
0,4,13,13,13,42,42,42,42,42,42,99
% ./hw1 </dev/null


% echo 11 10 9 10 11 | ./hw1
9x1 10x2 11x2
9,10,10,11,11

Standard Input                

If run without any redirection via < or |, then what should hw1 do? It should do what it always does: read from standard input. In this case, since standard input has not been changed with < or |, standard input remains connected to the keyboard. The program will appear to stop, but it is simply reading from the keyboard.                 

When that happens, the user has two options:

• Type control-C, which stops the current program. It’s also useful if your program goes into an infinite loop.
• Type some input for the program, as it’s expecting. When you're done, press control-D, which indicates end-of-file at a keyboard.

Hints                

• Produce a program called hw1, not HW1. They are different.
• Your program does not open a file. It reads from standard intput via cin. It does not use <fstream> or ifstream.
• The second line of output has a comma between each pair of integers. This is different than having a comma after every integer.
• This is a counting sort. Don’t store the input integers themselves. Instead, store counts. Your code must work if we feed it billions of integers.

    export STACK_FRAME_LINK_OVERRIDE=ffff-ad921d60486366258809553a3db49a4a

Requirements                

• The program may not store the incoming integers and sort them later. The program may not store the incoming integers at all, except to read them, one at a time, into the same variable.
• The program must store the counts as a plain C array of int of size 100, not in a vector, set, or any other advanced data structure.
• If the input has many integers, the very long output line will be too wide for a terminal. That’s ok.
• Error messages:
  • go to standard error
  • include the program name as given by argv[0].
  • stop the program
• If multiple things are bad, pick one, complain, and stop. You don’t have to mention all problems.
• Input format:
  • The input may contain arbitrarily many integers.
  • The input may consist of any number of lines.
  • Each input line may be arbitrarily long.
  • Each input line may contain any number of whitespace-separated integers, or perhaps none.
  • If an input integer is not in the range 0 to 99, inclusive (e.g., -42, or 65535), produce an error message mentioning the value of the bad integer.
  • The results are undefined if:
    • an input integer doesn’t fit into a C++ int
    • a given input integer appears too many times to count in an int
    • the input is not an integer (e.g., 3.4, fish, ⻥, or 🐟).
• Creativity is a wonderful thing, but your output format is not the place for it. Your output should look exactly like the output shown above.
  • UPPERCASE/lowercase matters.
  • Spaces matter.
  • Blank lines matter.
  • Extra output matters.
• You may not use any external programs. You many not use system(), fork(), popen(), execl(), execvp(), etc.
• You may not use C-style I/O such as printf(), scanf(), fopen(), and getchar().
  • Instead, use C++ facilities such as cout, cerr, and ifstream.
• You may not use endl. Use flush if needed.
• You may not use dynamic memory via new, delete, malloc(), calloc(), realloc(), free(), strdup(), etc.
  • It’s ok to implicitly use dynamic memory via containers such as string or vector.
• You may not use the eof() method.
• No global variables.
  • Except for an optional single global string called program_name containing argv[0].
• For readability, don’t use ASCII int constants (65) instead of char constants ('A') for printable characters.
• We will compile your program like this: cmake . && make
  • If that generates warnings, you will lose a point.
  • If that generates errors, you will lose all points.
• There is no automated testing/pre-grading/re-grading.
  • Test your code yourself. It’s your job.
  • Test with the CSU compilers, not just your laptop’s compiler.
  • Even if you only change it a little bit.
  • Even if all you do is add a comment.

If you have any questions about the requirements, ask. In the real world, your programming tasks will almost always be vague and incompletely specified. Same here.                 

Tar file                

• For each assignment this semester, you will create a tar file, and turn it in.
• The tar file for this assignment must be called: hw1.tar
• It must contain:
  • source files (*.cc)
  • header files (*.h) (if any)
  • CMakeLists.txt
• This command must produce the program hw1 (note the dot):

    cmake . && make

• At least  -Wall must be used every time g++ runs.

Remember how HW0 went on & on about testing your tar file? It applies here, too, and also to all other assignments.                 

How to submit your work:                

In Canvas, check in the file hw1.tar to the assignment “HW1”. It’s due 10:00:00ᴘᴍ MT Saturday, with a 24-hour late period for a 25% penalty.                 

How to receive negative points:                

Turn in someone else’s work.