Sale!

 CSC 310 Project 1 Sorting solution

Original price was: $35.00.Current price is: $28.00. $23.80

Category:

Description

5/5 - (1 vote)

Overview

This project is to implement two sorting algorithms. The first sorting algorithm is an 𝑂(𝑁
2
)
algorithm: either Selection Sort or Insertion Sort. The second algorithm is an 𝑂(𝑛𝑙𝑜𝑔𝑛) algorithm:
either Mergesort or Quicksort. If you choose Quicksort you must use the median-of-three method
to determine the pivot, and must use the Hoare Partition algorithm (both described in the book and
slides). With all of this done, you will be asked to gather some data about the running time and plot
it.

Requirements

You must implement the two sorting algorithms above. They should sort the numbers in ascending
order (smallest to largest). When you submit your project, you must have functioning code for both
sorting algorithms, but you can comment out the lines in your main method which actually do the
sorting (so I can uncomment a single line to switch the sorting algorithm). If you’d like, you can ask
the user which sorting algorithm and do it that way.

You must also have a function confirmSorted(). This function should take your array of numbers,
verify that it is sorted in ascending order, and return a Boolean. If the numbers are confirmed to be
sorted, print out “Confirmed sorted” and if they aren’t sorted, print out “Confirmed NOT sorted”. Do
this before and after the sort.

Data analysis

In addition to your code, you’ll be asked to try out each sorting algorithm will datasets of different
sizes and record the running time (in milliseconds). With this data, you should create a table and
graph like the one below. In a paragraph or two, please write what you’ve discovered with this data,
explain what is happening with the data and why.
Example Table Data
Size Insertion
Sort

Quicksort
10000 150 30
25000 400 80
50000 800 160
75000 1200 240
Example Graph

You will be provided with datasets of the following sizes: 10, 100, 1,000, 5,000, 10,000, 25,000,
50,000, 75,000, 100,000, 250,000, 500,000, 750,000, 1,000,000, and 10,000,000. Please include
results for all these datasets in your analysis. Some combinations of algorithm and dataset size
won’t be feasible and may be excluded (the slower algorithm will start to take a VERY long time with
large datasets).
0
500
1000
1500

10000 25000 50000 75000
Insertion Sort
Quicksort

Sample Output

Below is an idea of what kind of output your program should have.
Reading data from ‘100000.txt’.
Confirmed NOT sorted.
Sorting using Quicksort.
It took 150 ms.
Confirmed Sorted.

Getting Elapsed Time

All programming languages have ways to get elapsed time in milliseconds. The basic idea is to get
the time (in milliseconds) before sorting, after sorting, and then find the difference between them.
This can vary from language to language, so feel free to ask for help if you need it.

Programming Languages

You may use any programming language as long as you confirm it with me first. This course will be
centered on Java so that is my recommendation.

Grading

The assignment is worth 100 points. You will be graded on the following criteria:
Header comment block with name, class, date, project 10
𝑂(𝑁
2
) sorting algorithm sorts numbers correctly 20
𝑂(𝑛𝑙𝑜𝑔𝑛) sorting algorithm sorts numbers correctly 30
𝑂(𝑛𝑙𝑜𝑔𝑛) sorting algorithm meets requirements 10
The confirmSorted() method does what it should 10
Your data analysis is completed and conclusions are logical 20
Total 100
If your code doesn’t compile, there is an immediate 30 point penalty.

Submitting your work

Your work should be submitted as an archive (.zip, .7z, .rar) on Moodle. This archive must contain all
your source code files, as well as your data analysis document. The document can be in any
reasonable file format (PDF, .doc, .docx, .odt). Please do not submit your entire project folder.
This project is due Thursday, February 15 at 11:59pm.