Home

HW03: Single-variable Bubblesort

Name your code file memmanage.cpp. Include a Makefile that builds memmanage by running make, and has a make clean target that removes the binary memmanage.

Name your BitBucket repository exactly csci221-HW03. Test with the script /home/jeckroth/csci221/homework/HW03/grader.pl [bitbucketusername]

Task

Ask the user for some positive integers, and store them all in memory. When the user types 0, proceed to the next step (the user is done). You can assume less than 50 or so numbers will be entered. The values may be large (up to +/- 2 billion).

Show the numbers entered, in the order originally entered.

Then, sort the numbers, using the bubble sort algorithm given below.

Finally, print the numbers again in sorted order.


Do all of this with only 256 bytes of memory:

new char[256];

…and only one variable.

And no functions other than main(). And no array syntax. (No brackets apart from new char[256] above and possibly a delete[]).


And only one variable.


That single variable should probably hold the pointer to the start of the memory:

p = new char[256];

Also, don’t leak memory.

The test script will check that you only have one function, main(), and only one variable. It will also check that you use no brackets other than new char[256] and delete[] (you can use brackets in comments, if you want). It will also check for memory leaks by running through Valgrind.


Example run:

Enter a positive integer (0 to stop): 3
Enter a positive integer (0 to stop): 26
Enter a positive integer (0 to stop): 8
Enter a positive integer (0 to stop): 2
Enter a positive integer (0 to stop): 1
Enter a positive integer (0 to stop): 0
Entries (order entered): 3 26 8 2 1
Entries (sorted): 1 2 3 8 26

Bubble sort:

From: http://www.programmingsimplified.com/c/source-code/c-program-bubble-sort


int array[100], n, c, d, swap;

// fill array with values from user

for (c = 0; c < (n - 1); c++)
{
  for (d = 0; d < n - c - 1; d++)
  {
    if (array[d] > array[d+1])
    {
      swap       = array[d];
      array[d]   = array[d+1];
      array[d+1] = swap;
    }
  }
}

Note, the bubble sort code has 5 variables (array, n, c, d, swap) and array syntax ([brackets]). You are allowed 1 variable in your entire program and no array syntax.

CSCI 221 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.