Lab 06

SORT Sort

Objective:

I really like the word SORT! SORT SORT SORT SORT!  All SORTS of SORTS! Anyways, I like it so much that I want you to write a program to analyze some strings input from the user, count the number of times SORT (case doesn’t matter) appears in each string, then sort them from least number of SORT’s to most number of SORT’s!

Requirements:

• Functionality. (80pts)
• No Syntax Errors. (80pts*)
• *Code that cannot be compiled due to syntax errors is nonfunctional code and will receive no points for this entire section.
• Entering Data (10pts)
• The user must be able to enter any number of Strings that will be sorted.
• The Strings must be stored inside of a data structure; either an Array or a Data Structure of your own creation (like a Generic Linked List). Any other data structure imported or not of one’s own creation will result in a -80pts for Functionality.
• All the above must apply for full credit.
• Counting “Sort” (10pts)
• The program must then count the number of times the String “SORT” appears for each String.
• Case does not matter, so “SORT”, “sort”, or “sOrT” would all count.
• All the above must apply for full credit.
• Sorting “Sort” (50pts)
• Strings must be sorted based on the number of times that “SORT” appears from least to most.
• A sorting algorithm of one’s on creation must be used. Any use of automatic sorters will result in -80pts for Functionality.
• The program must use a sorting algorithm that is either O(nlg(n)) or Ɵ(nlg(n)) time complexity.
• All the above must apply for full credit.
• Printing the results and Restarting (10pts)
• Once sorted, the program must print out the results.
• Then the program must prompt the user if they would like to sort anymore Strings, and must restart if they choose to sort more Strings.
• All the above must apply for full credit.
• Coding Style. (10pts)
• Code functionality organized within multiple methods other than the main method, and methods organized within multiple classes where appropriate. (5pts)
• Readable Code (5pts)
• Meaningful identifiers for data and methods.
• Proper indentation that clearly identifies statements within the body of a class, a method, a branching statement, a loop statement, etc.
• All the above must apply for full credit.
• Comments. (10pts)
• Your name in the file. (5pts)
• At least 5 meaningful comments in addition to your name. These must describe the function of the code it is near. (5pts)

Example Dialog:

*The following Example Dialog demonstrates the interactions between a user and ONE possible implementation of the required software’s front-end / user interface. The software’s front-end / user interface may be implemented in MANY different ways and will receive full credit as long as it meets the most minimal of the above requirements. While you may use the example dialog as a guide, it is strongly encouraged to create the front-end / user interface in your own way. *

Key
Unhighlighted Text	Program’s Output
Highlighted Text	User’s Input

Enter any number of strings and I will sort by SORT’s.  Once you’re done entering sentences enter “quit”.

Sort

asdf

asdfsort

asdfasdfsortSortSORTsort

sortsortsortsortSORTSORTSORTSORT

qwertqwertqwertqwertsortSORT

sortzilla

quit

sort SORTED!

asdf

Sort

asdfsort

sortzilla

qwertqwertqwertqwertsortSORT

asdfasdfsortSortSORTsort

sortsortsortsortSORTSORTSORTSORT

Would you like to sort more Strings?

No

Goodbye!

Lab Report Questions:

1. Create a section named “Problem” and describe this lab’s problem in your own words. (10pts).
2. Create a section named “Solution Description” and describe how the code solves the problem in your own words. (10pts).
3. Create a section named “Problems Encountered” and describe the various syntax, run-time, and logic errors that were encountered while implementing the solution. (10pts)
4. Is f(n) = n, O(n²)? Describe why or why not.
5. Is f(n) = 2,000n³ + 1,000,000n² + 200n + 4, O(n³)? Desribe why or why not.
6. Is f(n) = n!, O(2ⁿ)? Describe why or why not.
7. What is the Big O time complexity for bubble sort?
8. What is the Big O time complexity for quick sort?
9. What is the Big O time complexity for merge sort?
10. In relation to time complexity, which is considered more efficient, Selection Sort or Merge Sort? Describe why.

Finally:

• Upload the source code (.JAVA File Extension) to LabSolution06
• And written lab report (DOC, .DOCX, or .PDF file extension) to LabReport06
• To Blackboard
• Following these instructions.
• If there are problems, then let the instructor know as soon as possible.