Question

In Java:

Write two advanced sorting methods of your choice: (Shell Sort OR Radix Sort) AND (Merge Sort OR Quick Sort). If you choose Shell Sort, experiment with different incremental sequences to see how they affect the algorithm's run time efficiency (count the number of comparisons and exchanges). If you choose to implement Radix Sort, answer the following question as well: Can you write a version of Radix Sort for String objects? If yes, explain how. If not, explain why.

Assume that input data is generated randomly and stored in a text file.

You will experiment with your program in two steps:

Step 1: Experimenting with a prototype data (integers from 1 to 10) to ensure that your implementation works correctly and the results match expectations. The results must be reported in a table format (not generated by the program, but collected manually from multiple program runs) in the a Word document as follows:

                 best case         worst case        average case

          char.1...char.N   char.1...char.N   char.1...char.N

alg.1        ...       ...             ...     ...                 ...      ...

alg.2        ...       ...             ...     ...                 ...      ...

  ...  

alg.N      ...       ...              ...     ...                 ...      ...

  

Step 2: Experimenting with large data sets of 2000 elements. The results must be reported in the same table format.

In addition, in the report, explain the empirical results generated by your program comparing them to the known theoretical results paying special attention to any discrepancies which must be clearly explained.

Must submit for grading: the java code, the random text file(s) generated by an independent module (you may need multiple random text files to better characterize the average efficiency of the respective algorithm), AND MOST IMPORTANTLY the report as explained above a Word document.

Answer 1

Insertion short

import java.util.*;
import java.lang.*;
import java.io.*;

class InsertionSort {
  
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
  
  
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
  
  
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
  
System.out.println();
}
  
  
public static void main(String args[])
{
int arr[] = { 10, 8, 9, 5, 2, 3, 1, 6, 4, 7 };
  
InsertionSort ob = new InsertionSort();
ob.sort(arr);
  
printArray(arr);
}
}

Output:- 1 2 3 4 5 6 7 8 9 10

Selection Short

import java.util.*;
import java.lang.*;
import java.io.*;

class SelectionSort
{
void sort(int arr[])
{
int n = arr.length;
  
  
for (int i = 0; i < n-1; i++)
{

int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
  
  
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
  

void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
  
  
public static void main(String args[])
{
SelectionSort ob = new SelectionSort();
int arr[] = {10, 8, 9, 5, 2, 3, 1, 6, 4, 7};
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}

Output:- 1 2 3 4 5 6 7 8 9 10