(Java program)

Use O-notation to describe the performance of simple blocks of code (i.e., 10 - 20 lines of code).

Describe multiple approaches to solving a problem, and intelligently dis- cuss the pros and cons of each approach

Background Info

Another algorithm for sorting an array of length n is Bubble Sort. This algo- rithm takes the following steps:

While the array is not sorted For each adjacent pair of elements

If the pair is not sorted Swap its elements.

Instructions

1. Give a run-through using a diagram, of how this algorithm would sort the array:

2. (a)

[ 6.1, 4.2, 3.3, 7.4, 5.5, 2.6, 8.7, 1.8 ]

Implement the algorithm in a static method called

 BubbleSorter.sort( ) 

(b) Run your static method on the following arrays of random integers:

i. size 10,000 ii. size 20,000 iii. size 30,000

iv. size 40,000 v. size 50,000 vi. size 60,000

Record the run-time of each array in milliseconds on a table. You should create the method .randomDoubleArray( ) class to help you create arrays. To keep track of run-time you may use the StopWatch class demoed in lecture.

(c) Plot the array size vs. the run-time.

Compute the big-Oh efficiency of the algorithm. Does the graph in part 2(c) agree with this efficiency?

Discuss the efficiency of Bubble Sort relative to Merge Sort and Selection Sort (Which is the most efficient on larger arrays? Which is the least efficient? Does efficiency change if the array size is small? ). Which algorithm you would use and when?

1 import java.util.Random; 2 public class BaubleSorter2 void bubleSorter2(double arr) int arrayLength -arr.length; for (int 1-0; 1 BaubleSorter2 (1) [Java Application] /Library/Java/JavaVirtualMachines/jdk1.8.0_144.jdk/Contents/Home/oin/java xception in thread "main" a.Arrayindex fBoundsEx 100 at BaubleSorter2.bubleSorter2(BaubleSorter at BaubleSorter2.main(BaubleSorter2.java:37) 1 import java.util.Random; 2 public class BaubleSorter2 void bubleSorter2(double arr) int arrayLength -arr.length; for (int 1-0; 1 BaubleSorter2 (1) [Java Application] /Library/Java/JavaVirtualMachines/jdk1.8.0_144.jdk/Contents/Home/oin/java xception in thread "main" a.Arrayindex fBoundsEx 100 at BaubleSorter2.bubleSorter2(BaubleSorter at BaubleSorter2.main(BaubleSorter2.java:37)