Program 1 350 Solution

Description

(first Github assignment… putting instructions on Google Drive so I can edit quickly)

Please e-mail me if you don’t see your e-mail in the list and do it from your USC e-mail. Also, include your GitHub Username.

Description:

You will code Quicksort

This is a shorter than usual because you may need more time to get your environment setup (you need Linux).Your code must run on the department Linux machines (1D43). If you have a separate Linux installation that you want to use, ssh over to the department machines to make sure nothing breaks or just go visit them.

SSH Instructions:

In Putty/MobaXTerm/WinSCP/Bitvise/… or just plain

SSH to l-1d43-XY.cse.sc.edu on port 222

• first character is a lowercase L
• XY=01 | 02 | … | 36

If you’re off campus, you will need to have Duo 2 Factor Authentication setup.

From a non-lab Linux machine can

ssh -p 222 <username>@l-1d43-XY.cse.sc.edu

Instructions:

Create an account on Github, if you haven’t already.

Go to this URL: https://classroom.github.com/a/_CEuazh1

Accept the Assignment

Follow the second link to the assignment.

Click on “Clone or download”

Copy the link

(if you’re remoting into the Linux labs, login and then switch to your ssh connection here)

<navigate to wherever you want to work>

git clone <the url>

The assignment repositories are private, so you’ll need to login.

git config –global –edit and edit the file

You can run the scoring function that builds and runs the tests for you and prints the score for you by running the following command (cd into the cloned directory first):

python3 score.py

You should see, “SCORE= 5” before you get any work done (one basic test will pass and, well, welcome to Git(Hub) if you’ve never been here before).

You can run the unit tests directly without using the score function (not necessary) with the following command, also from the downloaded directory.

cd program-1<username>

mkdir build && cd build

cmake ..

make

./runUnitTests

Implement Hoare Partitioning and Quicksort(all your code goes in src/quicksort.h)

Hoare Partition:

• Book Pseudocode:

• Code hoarePartition(T[],int,int) in src/quicksort.h
• Use whatever editor you’re accustomed to (nano/vim).
• If you’re working on your own machine, please make sure you test on a lab machine.
• Remember that the bounds are inclusive (the last parameter is the index of the last item, not one past it)
• You must use the medianOf3() to pick the pivot. Hoare Partition tests will fail if you do not. It returns the index of the item to use as pivot, the median of 3. Just swap() the median to the left position and then start the algorithm as in the book.
• You can use std::swap() (already included and all). This is overloaded in the library but you can probably just use as swap(A[i],A[j]), which is close to the book.
• A do-while loop is a natural replacement for a repeat except the test is flipped.
• The scans (array accesses) need to have the bounds checked (the book skips this). You may assume that it will only get called on a valid array of at least one item, however (a valid quicksort ensures this).
• The code is templated – it should work on most types. If you need to define a variable to hold the value of what’s in the array, do it as (the latter only works for ints):

T p = A[l];

not

int p =A[l];

• Indices are all ints, however.
• Test your code with python3 score.py
• 5 of 6 tests should pass. Note that score.py runs the tests one-by-one (you need to scroll to see all the tests). The other, direct way, runs them all one after the other but will crash if one of the tests segfaults.
• I added what I think are pretty useful error messages that show up above the summary (it dumps the array and gives some plain text error messages). Feel free to look at the targetgtest.cpp file (do not change it, however…)
• to see what’s going on; it helps to see how your code is getting called, sometimes.

Quicksort

• Book Pseudocode:

• Code quicksort(T[],int,int)
• Remember that the bounds are inclusive
• Most of the work was done in hoarePartition()
• Test as above, all six tests should pass.

Committing (backup and submission)

When I’m done or want to backup (git is for version control) I just

git add .

git commit -m “<some message>” // “final submission” makes sense if you’re done

git push origin master

We will grade the last submission up to the deadline (the very last submission until we won’t accept it anymore, possibly with a late penalty).

No need to submit code to dropbox.