Objective: The goal of this assignment is to practice sorting algorithms. Assign
ID: 3600571 • Letter: O
Question
Objective: The goal of this assignment is to practice sorting algorithms.
Assignment: In this assignment, you will be implementing versions of two sorting algorithms. You will use them to sort an array of strings in lexicographic order. All other requirements are listed below.
• You should write a method in a class named Runner1 that will generate an array of random strings for testing. The method should take in a number representing the size of the list, and return an array of that many Strings. Each string should have a randomly generated length between 3 and 10 (that is, 3 length 10).
• Implement another method in Runner1 to print out your array of strings. You should print a line for each string.
• As another preliminary step, implement a method CopyArray in Runner1 that creates a new array of strings with identical values of a given one.
• Now, write two methods inside Runner1, one named BubbleSort and the other named SelectionSort. Use parameters as you think appropriate. BubbleSort must implement the bubble sort algorithm we discussed in the class and SelectionSort must implement the selection sort algorithm we discussed in class. Note that both BubbleSort and SelectionSort must sort the strings given in the input array in lexiographic order.
• Demonstrate that your code works by generating a random list of 20 strings (in an array), printing out the list before you sort it, and then printing out the list again after it is sorted using BubbleSort. For an identical list of 20 strings (copied right after the generation of the array that was given to BubbleSort as an input), show the list before and after the use of the SelectionSort method.
• Write a class named Runner2 that will test the speed of your BubbleSort and SelectionSort methods by recording the time needed to sort an array of different number of Strings (For example, 2000, 3000, 4000, 5000, 6000, and 7000 Strings). Using this data, draw two lines on the same line-plot using MS Excel, one line for Bubble Sort and one for Selection Sort, where x-axis is the number of Strings in the array and y-axis is the runtime. On the MS Word document, (1) copy the plot and paste it, (2) report the configuration (processor speed and model, memory, and operating system) of the computer where you executed Runner2, (3) write what are the time complexities of Bubble sort and Selection sort algorithms, (4) write no more than four sentences on if (and how) your plot demonstrates the expected time complexities of Bubble sort and Selection sort algorithms. Submit the MS Word file with your source codes. Convert/Export your MS Word file to a PDF file and submit it with all other files.
Explanation / Answer
Runner1 sorts array of strings of size 20 using BubbleSort and SelectionSort.
Runner2 sorts array of strings of size 2000-7000 using BubbleSort and SelectionSort.
The outputs have been given clearly with time taken for th sorts for the same array using 2 different sorting techniques.
MS Word File and PDF are not possible to upload. I hope you can plot the data from the outputs.
If you need any help feel free to approach. The time in the output are in millis.
The outputs have also been provided.
Kindly see the code below. If you have any queries. Kindly comment.
*******************************************************************
import java.util.Arrays;
public class Runner1 {
private static final String ALPHA_NUMERIC_STRING = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
public static String randomAlphaNumeric(int count) {
StringBuilder builder = new StringBuilder();
while (count-- != 0) {
int character = (int) (Math.random() * ALPHA_NUMERIC_STRING.length());
builder.append(ALPHA_NUMERIC_STRING.charAt(character));
}
return builder.toString();
}
public static String[] CopyArray(String[] source) {
return Arrays.copyOf(source, source.length);
}
public static int random() {
int randomNum = (1 + (int) (Math.random() * 7)) + 3;
return randomNum;
}
public static void bubbleSort(String arr[]) {
int n=arr.length;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (arr[j - 1].compareTo(arr[j])>0) {
// swap elements
String temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void selectionSort(String[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j].compareTo(arr[index])<0){
index = j;//searching for lowest index
}
}
String smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
public static void main(String[] args) {
String test1[] = new String[20];
String test2[] = new String[20];
for(int i=0;i<test1.length;i++)
{
test1[i]=randomAlphaNumeric(random());
}
test2=CopyArray(test1);
System.err.println("Input Array1:");
System.out.println(java.util.Arrays.toString(test1));
bubbleSort(test1);
System.err.println("Sorted Array1:");
System.out.println(java.util.Arrays.toString(test1));
System.err.println("Input Array2:");
System.out.println(java.util.Arrays.toString(test2));
selectionSort(test2);
System.err.println("Sorted Array2:");
System.out.println(java.util.Arrays.toString(test2));
}
}
public class Runner2 {
public static void main(String[] args) {
int lengths[]= {2000,3000,4000,5000,6000,7000};
long startTime,stopTime,elapsedTime;
for(int i=0;i<lengths.length;i++) {
String array1[]= new String[lengths[i]];
String array2[]= new String[lengths[i]];
for(int j=0;j<lengths[i];j++)
{
array1[j]=Runner1.randomAlphaNumeric(Runner1.random());
}
array2=Runner1.CopyArray(array1);
System.out.println(" Total number of strings to be sorted= "+lengths[i]);
startTime = System.nanoTime();
Runner1.bubbleSort(array1);
stopTime = System.nanoTime();
elapsedTime = stopTime - startTime;
System.out.println("Bubble sort takes (in millis): "+elapsedTime/1000000);
startTime = System.nanoTime();
Runner1.selectionSort(array2);
stopTime = System.nanoTime();
elapsedTime = stopTime - startTime;
System.out.println("Selection sort takes (in millis): "+elapsedTime/1000000);
}
}
}
****************************************************************************
Sample outputs:
Sample output for Runner1 sorting 20 strings using BubbleSort and SelectionSort:
Input Array1:
[HcSQH, 6FJylLUTeL, Z9mJ2G3DQ, ajAI5at6, U9JE, J881yM7w, 6RJTR, qkiFIGtoW, bKDwSAD6, eBTyGdYmzm, qn3LCUWu7, Nfz4Z, R1W1d2qQ, 3o54Z, KvCmY3, lOLa21, ARd0417Q5J, UyRQPN, DJFC, dH3n7fnt]
Sorted Array1:
[3o54Z, 6FJylLUTeL, 6RJTR, ARd0417Q5J, DJFC, HcSQH, J881yM7w, KvCmY3, Nfz4Z, R1W1d2qQ, U9JE, UyRQPN, Z9mJ2G3DQ, ajAI5at6, bKDwSAD6, dH3n7fnt, eBTyGdYmzm, lOLa21, qkiFIGtoW, qn3LCUWu7]
Input Array2:
[HcSQH, 6FJylLUTeL, Z9mJ2G3DQ, ajAI5at6, U9JE, J881yM7w, 6RJTR, qkiFIGtoW, bKDwSAD6, eBTyGdYmzm, qn3LCUWu7, Nfz4Z, R1W1d2qQ, 3o54Z, KvCmY3, lOLa21, ARd0417Q5J, UyRQPN, DJFC, dH3n7fnt]
Sorted Array2:
[3o54Z, 6FJylLUTeL, 6RJTR, ARd0417Q5J, DJFC, HcSQH, J881yM7w, KvCmY3, Nfz4Z, R1W1d2qQ, U9JE, UyRQPN, Z9mJ2G3DQ, ajAI5at6, bKDwSAD6, dH3n7fnt, eBTyGdYmzm, lOLa21, qkiFIGtoW, qn3LCUWu7]
Sample output for Runner2 sorting strings using BubbleSort and SelectionSort with different length and time is given below:
Total number of strings to be sorted= 2000
Bubble sort takes (in millis): 42
Selection sort takes (in millis): 26
Total number of strings to be sorted= 3000
Bubble sort takes (in millis): 78
Selection sort takes (in millis): 34
Total number of strings to be sorted= 4000
Bubble sort takes (in millis): 124
Selection sort takes (in millis): 41
Total number of strings to be sorted= 5000
Bubble sort takes (in millis): 170
Selection sort takes (in millis): 80
Total number of strings to be sorted= 6000
Bubble sort takes (in millis): 236
Selection sort takes (in millis): 96
Total number of strings to be sorted= 7000
Bubble sort takes (in millis): 341
Selection sort takes (in millis): 143
****************************************************************************
I hope this helps you.
If you find my answer helpful,
Kindly rate the answer.
All the best :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.