Design an OO framework that will allow you to study multiple sorts. All of the o
ID: 3558220 • Letter: D
Question
Design an OO framework that will allow you to study multiple sorts. All of the objects in the sorting framework will need to sort the same array of data and time the results. After you have run your program on data with different characteristics, you will need to write a report detailing your results.
To see how well the sorts work, you must sort arrays of varying sizes. These sizes are: 10 elements, 50 elements, 100 elements, 500 elements, and 1000 elements. For each of these array sizes, you will have to use one array that is already sorted, another array that is partially sorted, and one that is random. Create a table containing the runtime of each of the sorts when sorting these combinations.
I really have no idea how to even get started on this since Java is completely new to me. If I could just get pointers with how to go about doing this, I would be happy. I am not willing to provide information for payment, so please do not offer that.
Explanation / Answer
/**Sort.java Main File**/
package sorting;
import java.util.Random;
public class Sort {
static int c1=0,c2=0,c3=0,c4=0;
public static void main(String[] args) {
//Set the size of the Array
int size = 10;
//Create a new Array of this size
int[] A = new int[size];
int[] B = new int[size];
int[] C = new int[size];
int[] D = new int[size];
int[] E = new int[size];
//Create and object of Random class to create random numbers
Random rand = new Random();
System.out.println("Filling up the Array with random numbers!");
//Fill up the Arrays with same random numbers between 1 and 100
for(int i=0;i<size;i++){
int n = rand.nextInt(100)+1;
A[i] = n;
B[i] = n;
C[i] = n;
D[i] = n;
E[i] = n;
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/****************** Bubble Sort Begin ***************/
//Note the starting time before Bubble Sort
long startTime = System.nanoTime();
//Call the recursiveQuickSort method to sort the array
BubbleSort.bubbleSort(A, size);
//Note the End time after Bubble Sort
long endTime = System.nanoTime();
//Calculate the time elapsed in Bubble Sort
long timeElapsed = endTime - startTime;
//Print the time elapsed in Bubble Sort
System.out.println(" Bubble sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/****************** Bubble Sort End *****************/
/****************** INSERTION SORT BEGIN ********************/
//Note the starting time before Insertion Sort
startTime = System.nanoTime();
//Execute Insertion Sort
InsertionSort.insertionSort(B, size);
//Note the End time after Insertion Sort
endTime = System.nanoTime();
//Calculate the time elapsed in Insertion Sort
timeElapsed = endTime - startTime;
//Print the time elapsed in Insertion Sort
System.out.println("Insertion sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(B[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/********************** INSERTION SORT END ********************/
/********************** MERGE SORT BEGIN *******************/
//Note the starting time
startTime = System.nanoTime();
//Execute Merge Sort
MergeSort.mergeSort(C, 0, size-1);
//Note the End time
endTime = System.nanoTime();
//Calculate the elapsed time
timeElapsed = endTime - startTime;
//Print the elapsed time
System.out.println(" Merge sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(C[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/******************** MERGE SORT END ********************/
/******************** Quick Sort Begin *****************/
//Note the starting time before Quick Sort
startTime = System.nanoTime();
//Call the recursiveQuickSort method to sort the array
QuickSort.recursiveQuickSort(D, 0, size-1);
//Note the End time after Quick Sort
endTime = System.nanoTime();
//Calculate the time elapsed in Quick Sort
timeElapsed = endTime - startTime;
//Print the time elapsed in Quick Sort
System.out.println(" Quick sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(D[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/********************** Quick Sort End *********************/
/********************** SELECTION SORT BEGIN *******************/
//Note the starting time
startTime = System.nanoTime();
//Execute Selection Sort
SelectionSort.selectionSort(E, size);
//Note the End time
endTime = System.nanoTime();
//Calculate the elapsed time
timeElapsed = endTime - startTime;
//Print the elapsed time
System.out.println(" Selection sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(E[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/******************** SELECTION SORT END ********************/
}
}
/**BubbleSort.java**/
package sorting;
import java.util.Random;
public class BubbleSort {
public static void bubbleSort( int a[], int n ){
int i, j,t=0;
for(i = 0; i < n; i++){
for(j = 1; j < (n-i); j++){
if(a[j-1] > a[j]){
t = a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}
}
}
public static void main(String[] args) {
//Set the size of the Array
int size = 500;
//Create a new Array of this size
int[] A = new int[size];
//Create and object of Random class to create random numbers
Random rand = new Random();
System.out.println("Filling up the Array with random numbers!");
//Fill up the Array with random numbers between 1 and 100
for(int i=0;i<size;i++){
int n = rand.nextInt(100)+1;
A[i] = n;
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
//Note the starting time before Quick Sort
long startTime = System.nanoTime();
//Call the recursiveQuickSort method to sort the array
bubbleSort(A, size);
//Note the End time after Insertion Sort
long endTime = System.nanoTime();
//Calculate the time elapsed in Insertion Sort
long timeElapsed = endTime - startTime;
//Print the time elapsed in Insertion Sort
System.out.println(" Bubble sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
}
}
/**InsertionSort.java**/
package sorting;
import java.util.Random;
public class InsertionSort {
public static void insertionSort (int data[],int n) {
int tmp,i,j;
for (j=1; j<n; j++) {
i =j - 1;
tmp = data[j];
while ( (i>=0) && (tmp < data[i]) ) {
data[i+1] = data[i];
i--;
}
data[i+1] = tmp;
}
}
public static void main(String args[]){
//Set the size of the Array
int size = 500;
//Create a new Array of this size
int[] A = new int[size];
//Create and object of Random class to create random numbers
Random rand = new Random();
System.out.println("Filling up the Array with random numbers!");
//Fill up the Array with random numbers between 1 and 100
for(int i=0;i<size;i++){
int n = rand.nextInt(100)+1;
A[i] = n;
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/****************** INSERTION SORT BEGIN ********************/
//Note the starting time before Insertion Sort
long startTime = System.nanoTime();
//Execute Insertion Sort
insertionSort(A, size);
//Note the End time after Insertion Sort
long endTime = System.nanoTime();
//Calculate the time elapsed in Insertion Sort
long timeElapsed = endTime - startTime;
//Print the time elapsed in Insertion Sort
System.out.println("Insertion sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/********************** INSERTION SORT END ********************/
}
}
/**MergeSort.java**/
package sorting;
import java.util.Random;
public class MergeSort
{
public static void main(String[ ] args)
{
//Set the size of the Array
int size = 10;
//Create a new Array of this size
int[] A = new int[size];
//Create and object of Random class to create random numbers
Random rand = new Random();
System.out.println("Filling up the Array with random numbers!");
//Fill up the Array with random numbers between 1 and 100
for(int i=0;i<size;i++){
int n = rand.nextInt(100)+1;
A[i] = n;
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/********************** MERGE SORT BEGIN *******************/
//Note the starting time
long startTime = System.nanoTime();
//Execute Selection Sort
mergeSort(A, 0, size-1);
//Note the End time
long endTime = System.nanoTime();
//Calculate the elapsed time
long timeElapsed = endTime - startTime;
//Print the elapsed time
System.out.println(" Merge sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/******************** MERGE SORT END ********************/
}
static public void DoMerge(int [] numbers, int left, int mid, int right)
{
int [] temp = new int[25];
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while (left <= left_end)
temp[tmp_pos++] = numbers[left++];
while (mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i = 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
public static void mergeSort(int [] numbers, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
mergeSort(numbers, left, mid);
mergeSort(numbers, (mid + 1), right);
DoMerge(numbers, left, (mid+1), right);
}
}
}
/**QuickSort.java**/
package sorting;
import java.util.Random;
public class QuickSort {
public static void main(String[] args) {
//Set the size of the Array
int size = 500;
//Create a new Array of this size
int[] A = new int[size];
//Create and object of Random class to create random numbers
Random rand = new Random();
System.out.println("Filling up the Array with random numbers!");
//Fill up the Array with random numbers between 1 and 100
for(int i=0;i<size;i++){
int n = rand.nextInt(100)+1;
A[i] = n;
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
//Note the starting time before Quick Sort
long startTime = System.nanoTime();
//Call the recursiveQuickSort method to sort the array
recursiveQuickSort(A, 0, size-1);
//Note the End time after Insertion Sort
long endTime = System.nanoTime();
//Calculate the time elapsed in Insertion Sort
long timeElapsed = endTime - startTime;
//Print the time elapsed in Insertion Sort
System.out.println(" Quick sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
}
/**
* Partition logic
*
* @param a array to be modified based on pivot
* @param left lower bound of the array
* @param right upper bound of the array
* @return the partition index where elements to its left are less than it and
* elements to its right are more than it
*/
public static int partition(int[] a, int left, int right) {
// Get the pivot element
int pivot = a[left];
// Break when left is > right
while(left <= right) {
//increment the lower bound till you find the element more than the pivot
while(a[left]<pivot)
left++;
//decrement the upper bound till you find the element less than the pivot
while(a[right]>pivot)
right--;
// swap the values which are left by lower and upper bounds
if(left <= right) {
int tmp = a[left];
a[left] = a[right];
a[right] = tmp;
//increment left index and decrement right index
left++;
right--;
}
}
return left;
}
/**
* Recursive quickSort logic
* @param a input array
* @param i start index of the array
* @param j end index of the array
*/
public static void recursiveQuickSort(int[] a, int i, int j) {
// Handle logic to divide the array
int pivot_index = partition(a, i, j);
// Recursively call quick sort with left part of the divided array
if(i<pivot_index-1) {
recursiveQuickSort(a, i, pivot_index-1);
}
// Recursively call quick sort with right part of the divided array
if(j>pivot_index) {
recursiveQuickSort(a, pivot_index, j);
}
}
}
/**SelectionSort.java**/
package sorting;
import java.util.Random;
public class SelectionSort {
public static void selectionSort(int array[], int n){
for(int x=0; x<n; x++){
int index_of_min = x;
for(int y=x; y<n; y++){
if(array[index_of_min]>array[y]){
index_of_min = y;
}
}
int temp = array[x];
array[x] = array[index_of_min];
array[index_of_min] = temp;
}
}
public static void main(String[] args) {
//Set the size of the Array
int size = 500;
//Create a new Array of this size
int[] A = new int[size];
//Create and object of Random class to create random numbers
Random rand = new Random();
System.out.println("Filling up the Array with random numbers!");
//Fill up the Array with random numbers between 1 and 100
for(int i=0;i<size;i++){
int n = rand.nextInt(100)+1;
A[i] = n;
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/********************** SELECTION SORT BEGIN *******************/
//Note the starting time
long startTime = System.nanoTime();
//Execute Selection Sort
selectionSort(A, size);
//Note the End time
long endTime = System.nanoTime();
//Calculate the elapsed time
long timeElapsed = endTime - startTime;
//Print the elapsed time
System.out.println(" Selection sort took " + timeElapsed + " nano seconds");
//Display the contents of the Array after sorting
System.out.println(" Contents of the Array after sorting: ");
for(int i=0;i<size;i++){
System.out.print(A[i] + " ");
if(i%20 == 0 && i!=0) System.out.println();
}
/******************** SELECTION SORT END ********************/
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.