Sorting: Implementing an Existing Sort

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). If you are backing your program with a linked list, great! If using an array, assume the potential for a very large dataset, conceivably on the order of 500,000. (Yes, 500000).
• 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.
• Allow the user to select which sorting algorithm to use (your naive sort, or the sort you are implementing here).
• Time the running of the chosen sort (naive or your selected sort). You can time things with the clock(3) or time(3) functions (be sure to include proper header files).

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).
• Each sort must be located with its own function, and called from your central program loop. Have each sort function accept the same type, quantity, and order of parameters, and return the same value.
• If you are in Data Structures, this is an excellent program to practice using Linked Lists in. Singly or Doubly can work– here you will find the benefit of their near-infinite expandability.
• 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. But remember, freakishly large arrays (note there may be an upper limit– I pulled 500,000 out of the air hoping it wouldn't be too big… but your program logic should be able to easily work with values larger than 500,000).

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

lab46:~/src/discrete/p07$ ./sortprog

   -============-
[[[ Sort Program ]]]
   -============-

   1>Enter values
   2>Naively Sort
   3>SelectedSort
   4>Display List
   5>Quit for now

] 1

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

   -============-
[[[ Sort Program ]]]
   -============-

   1>Enter values
   2>Naively Sort
   3>SelectedSort
   4>Display List
   5>Quit for now

] 4
Displaying current list:
    37, 73, 57, 75, 73, 4, 32, 1
    
   -============-
[[[ Sort Program ]]]
   -============-

   1>Enter values
   2>Naively Sort
   3>SelectedSort
   4>Display List
   5>Quit for now

] 3
List Sorted! Process took 4204 mS.

   -============-
[[[ Sort Program ]]]
   -============-

   1>Enter values
   2>Naively Sort
   3>SelectedSort
   4>Display List
   5>Quit for now

] 4
Displaying current list:
    1, 4, 32, 37, 57, 73, 73, 75
  

   -============-
[[[ Sort Program ]]]
   -============-

   1>Enter values
   2>Naively Sort
   3>SelectedSort
   4>Display List
   5>Quit for now

] 5  
lab46:~/src/discrete/p07$ 

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 well 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).
• Your code must make appropriate use of functions.
• Your working, compilable code should be added/commit/pushed to your repository located in the ~/src/discrete/submit/p07/ directory.