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.

â€¢ Download SortsTestHarness.java or SortsTestHarness.py to test your code.

â€¢ Download the RandomNames7000.csv.

Note:

Java Students: Please adhere to the Java Coding Standard document located

under Links and Resources on Blackboard.

Python Students: Please adhere to the PEP8 Coding Standard.

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)

Hint: You can run multiple test cases by adding additional

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.

Purchase answer to see full

attachment