Question

Perform the following traces and submit your answer.

• Write the letters in your name as a sequence without spaces (first name, middle name, last name). In my case the sequence is: CARLOSSILVA.submit a trace of how the 2 merge sorts algorithms will sort the letter in alphabetic order. In my example the sort result will be: AACILLORSSV . Be sure, that each step of the algorithm is clearly presented in the result table.
• a tracing for Down Merge Sort
• a tracing for Bottom Up Merge Sorts

Answer 1

//java program

import java.util.Scanner;

public class Sortname {
public static void main(String args[]) {
   Scanner in = new Scanner(System.in);
  
   String input ;
   System.out.println("Enter name : ");
   input = in.nextLine();
   char[] name1 = input.toCharArray();
   char[] name2 = input.toCharArray();
   char[] name3 = input.toCharArray();
     
   selectionsort(name1 , name1.length);
   insertionsort(name2 , name2.length);
   shellsort(name3 , name3.length);
     
   System.out.println(name1);
   System.out.println(name2);
   System.out.println(name3);
  
   in.close();
}
public static void selectionsort(char a[],int n){int min;
   for(int i=0;i<n-1;i++){
       min=i;
       for(int j=i+1;j<n;j++)if(a[j]<a[min])min=j;
       if(min!=i){
           char temp=a[i];
           a[i]=a[min];
           a[min]=temp;
       }
   }
}

public static void insertionsort(char a[],int n){
   for(int i=1;i<n;i++){
       int j=i-1;
       char val=a[i];
       while(j>=0&&a[j]>val){
       a[j+1]=a[j];
       j--;}
       a[++j]=val;
   }
}

public static void shellsort(char arr[], int n)
{
for (int gap = n/2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i += 1)
{
char temp = arr[i];
  
int j;   
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];

arr[j] = temp;
}
}
  
}
}

//sample output