Objectives of this Lab To actually write code for two sorting algorithms: bubble

Question

Objectives of this Lab

To actually write code for two sorting algorithms: bubble and selection sort, and

to see the difference in performance between these and quicksort provided by Java.

Description

This lab requires you to complete the Sorting.java class, which implements four different sorting algorithms: bubble, selection, insertion, and quicksort. For this lab, the insertion sorting code is provided as an example, and quicksort is provided by Java in the form of the Arrays.sort() method. Arrays.sort() uses quicksort for primitives and mergesort for objects. A second class named FillArray.java provides a couple of useful methods for filling an array with random numbers and checking whether an array is sorted. Here are the two methods you must implement:

Instructions

Make an Eclipse project named R21.

Download Sorting.java and FillArray.java.

Look through the provided code, which your TA will help explain.

First, complete the bubbleSort method in Sorting.java.

Second, complete the selectionSort method in Sorting.java.

HINT 1: These algorithms are documented on the Internet.

HINT 2: Start with 10 elements and uncomment debug code in FillArray.java.

The provided code will verify your sorting code and measure performance.

When your sorting code is verified, measure performance with 50000 elements.

Testing

Here is the approximate output of the program after all methods and test code are complete, for sorting 50000 elements. Don't worry about your output exactly matching, since your performance may vary somewhat:

Explanation / Answer

// Bubble sorting
public static void bubbleSort(double[] arr) {
// Put the code for bubble sort here
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]){
// swap temp and arr[i]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

// Selection sorting
public static void selectionSort(double[] arr) {
// Put the code for selection sort here
int n = arr.length;

// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

public static void main(String args[]) {

       long start, end;

       double arr[] = new double[50000];

       fillArray(arr);

       start = System.currentTimeMillis();

       bubbleSort(arr);

       end = System.currentTimeMillis();

       System.out.println("Bubble sort of 50000 elements = " + (end-start) + " milliseconds.");

       start = System.currentTimeMillis();

       selectionSort(arr);

       end = System.currentTimeMillis();

       System.out.println("Selection sort of 50000 elements = " + (end-start) + " milliseconds.");

   }

NOTE: Here, I have provided the implementation of bubble sort and selection sort. For performance analysis, you need to provide the implementation of FillArray.java too.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.