# CS 5040: Data Structures and Algorithms

Stuck on a homework question? Our verified tutors can answer all questions, from basic math to advanced rocket science!

Spring 2021, Assignment #4 – Sorting

Common caution:

Design the program such that it is interactive, allowing the user to re-enter different inputs during the same run session. Use a proper prompt such “Do you want to re-run code with different inputs (Y/N)?” If the user enters Y, the program then prompts the user for new inputs. Otherwise, the program terminates. Document your code and organize the outputs properly. See submission and grading instructions above.

Note:  Only complete and correct code receives credit. Code must compile and run on its own as received. Using code from outside sources receives NO credit.

Do not treat or manipulate input values as strings at any point for this assignment. They are manipulated as numeric integer values throughout the assignment.

Part 1: (20 points)

Implement the Quick Sort algorithm. Write a recursive method which is discussed in our class. Call the program QuickSortYourName.java. The program prompts the user to enter the number of input values, then reads that many positive integer values and store them in an array of type integer (call it inputs). Again, the program applies quick sort algorithm we discussed to the values stored in array inputs, and then prints out the content of the array before and after being sorted.

How many integer numbers do you have?: 6          //  <- user input

Enter 6 integer numbers: 213 3465 7 29 541 45    //  <- user input

——————————————————

Inputs array before sorting (quick):  213, 3465, 7, 29, 541, 45

Inputs array after sorting (quick):   7, 29, 45, 213, 541, 3465

Part 2: (20 points)

Use given class Queue.java to implement the Radix Sort algorithm using queues we discussed in class. Call the program RadixSortYourName.java. The program prompts the user to enter the number of input values, then reads that many positive integer values and store them in an array of type integer (call it inputs). Again, the program applies radix sort algorithm we discussed to the values stored in array inputs, and then prints out the content of the array before and after being sorted. (There is no limitation of the number of digits of each integer. For example, your program must available on any integer possible number such as 492195 or 9817352)

How many integer numbers do you have?: 6          //  <- user input

Enter 6 integer numbers: 213 3465 7 29 541 45    //  <- user input

——————————————————

Inputs array before sorting (radix):  213, 3465, 7, 29, 541, 45

Inputs array after sorting (radix):   7, 29, 45, 213, 541, 3465

Notice that we are using ONLY one array (inputs).

Radix sort requires digit extraction. To do so, implement a separate method in class RadixSort (call it ExtractDigit(…)) to do this function. See class notes on how to do digit extraction from a numeric value. You also need to implement another method to do digit count in a number.

Submission:
Before submitting your programs, make sure you review the assignment submission requirements and grading guidelines on the course webpage. The grading guidelines explain some of the common errors found in programming assignments.

1. One document with screenshots to show all your results, all individual .java files.
2. The assignment is due no later than 11:59 PM on the due day posted in D2L.
3. Please compile and run your java files (only the .java files) right before you upload to the assignment submission folder in D2L.