User Tools

Site Tools


haas:fall2013:common:discrete-p04-20121016142000

Sorting: Naive Sort

Overview

With our covering of sets, algorithms, algorithmic complexity, and efficiency, it makes sense to reinforce those concepts through code. I'd like you to develop the beginnings of a program that will demonstrate various sorting algorithms, starting with your own best attempt implementation, aka the naive sort.

By naive sort, I want you to try your best at implementing a sort based on your current pool of programming and problem solving experience; do NOT look up any of the common established sorting algorithms for this, as it will taint your ability to create a naive sort.

Don't worry, the other sorts will be soon to follow.

Criteria

Write a program that does the following:

  • Prompt the user to input a value (the elements), keep reading them in until the user specifies a terminating value (say, -1). This
  • You should allow for duplicate values.
  • Once the initial building is complete, display numbers both before and after the sort has taken place.
  • Sort from least to greatest, solving the problem based on your current programming experience.

Assumptions

You may develop the program with the following assumptions in mind:

  • Stick to one type of data (byte-valued whole numbers, ASCII chars, etc. don't try to be universal).
  • In future iterations of this program, we'll be implementing other sorting algorithms, so you may want to ensure a certain level of modularity.
  • If you are in Data Structures, this is an excellent program to practice using Linked Lists in. Singly or Doubly can work.
  • If you are not in Data Structures, obviously you'll want to use some sort of container, and if you're not familiar with Linked Lists, you've really only got one choice remaining: arrays.
  • If using an array, you obviously will have to assume a max size.

Example Output

You resulting program should operate in a manner similar to the following (output doesn't have to exactly match):

lab46:~/src/discrete/p04$ ./sortprog
Enter a unique value (-1 to quit): 37
Enter a unique value (-1 to quit): 73
Enter a unique value (-1 to quit): 57
Enter a unique value (-1 to quit): 75
Enter a unique value (-1 to quit): 73
Enter a unique value (-1 to quit): 4
Enter a unique value (-1 to quit): 32
Enter a unique value (-1 to quit): 1
Enter a unique value (-1 to quit): -1

Before Sorting: 37, 73, 57, 75, 73, 4, 32, 1
 After Sorting: 1, 4, 32, 37, 57, 73, 73, 75

lab46:~/src/discrete/p04$ 

Submission

I will be evaluating your program one-on-one at the start of class, when this is due. If you do not show up, you will not receive credit any for it.

Please be sure your program also meets the following criteria:

  • Codebase is documented. You must have comments sprinkled throughout your code.
  • Code is uniformly and optimized for readability in its indentation. I will be evaluating indentation!
  • Your code must compile and run, without warnings or issues, with the above requirements (I may ask for specific values to be input).
  • You MUST show both before and after.
  • Your code must adequately as requested.
  • Your working, compilable code should be added/commit/pushed to your repository located in the ~/src/discrete/submit/p04/ directory.
haas/fall2013/common/discrete-p04-20121016142000.txt · Last modified: 2012/09/30 16:01 by 127.0.0.1