+1(978)310-4246 credencewriters@gmail.com
Select Page

Practical – Files and Sorting
Aims
â€¢ To implement and test Bubble Sort, Insertion Sort and Selection Sort.
â€¢ To parse and sort the data in a file.
Before the Practical
â€¢ Read this practical sheet fully before starting.
â€¢ Download Sorts.java or Sorts.py from Blackboard. Use this as a starting point
to writing the sorting methods.
Note:
under Links and Resources on Blackboard.
Activities
1. Bubble Sort Implementation
Time to write some code:
â€¢ In Sorts.java/.py, implement the bubbleSort() method using the pseudocode
from the lecture slides as a guide.
â€¢ Donâ€™t forget to include a check to stop bubbleSort() if it does not do any swaps
during a pass (i.e., The array has finished being sorted).
â€¢ Note: The method in the Sorts.java/py file works on an int[] array.
â€¢ Test your code using the SortsTestHarness.java/py
java SortsTestHarness n xy …
python3 SortsTestHarness.py n xy …
where:
n is the number of integers to sort
x is one of:
b – bubble sort
i – insertion sort
s – selection sort
y is one of:
a – 1..n ascending
d – 1..n descending
r – 1..n in random order
n – 1..n nearly sorted (10% moved)
Command Line Arguments.
2. Selection Sort Implementation
Do the same for Selection Sort as you did for Bubble Sort.
â€¢ Selection Sort differs from Bubble Sort in that it only swaps once per pass.
Instead, what it does is search for the smallest value, update the index of the
smallest value until the end of the pass. Only then, does it swap the smallest
value with the first value.
â€“ Remember that in the second pass, the first value has already been sorted.
Therefore, donâ€™t include the first value in the second pass
â€“ The same is true for subsequent passes (i.e., The third pass should ignore
the first two values.).
â€¢ Test your code using the SortsTestHarness.java/py.
3. Insertion Sort Implementation
Do the same for Insertion Sort as you did for Bubble Sort and Selection Sort.
â€¢ Test your code using the SortsTestHarness.java/py.
4. Exploring Sorting Runtimes
SortsTestHarness.java/py lets you easily test your sorts code for various types of
data. (Refer to Activity 1)
â€¢ Create a table of runtime results, using at least four array sizes and at least three
of the ascending/descending/random/nearly sorted options across each of the
implemented sorting algorithms.
â€¢ Write a paragraph discussing the results in terms of time complexity and other
characteristics of the sorting algorithms.
â€¢ Hint: Identify the average/best/worst cases and investigate the scalability of the
sorting algorithms.
5. Sorting a File
Now you can try sorting a file of random student numbers and names:
â€¢ Parse the file to read in the Student IDs into an array.
â€¢ Sort the data using each of the sorting algorithms and output the sorted array
into a .csv file.
â€¢ Challenge: You can read in the Student ID and Student Name into an object.
(Not required, but highly beneficial for subsequent practicals.)
Marking Guide
Your submission will be marked as follows:
â€¢ [2] Bubble Sort is implemented properly and tests correctly.
â€¢ [2] Selection Sort is implemented properly and tests correctly.
â€¢ [2] Insertion Sort is implemented properly and tests correctly.
â€¢ [2] Sorts performance investigation.
â€¢ [2] File reading and sorting.