Write a single program to compare between insertion sort and selection sort. For

Question

Write a single program to compare between insertion sort and selection sort. For a given input array, write separate functions to implement insertion sort and selection sort algorithms and perform the below tasks: 1. The program should output number of comparisons and data movements made by each algorithm. 2. The program should show intermediate steps(arrays) of the sorting process by each algorithm. 3. The program should have a mechanism to ask the user to To Continue/Quit" the program. suppose if user inputs 1, the program should re-run from the beginning asking for another run on a different input. If user inputs 0, the program should stop. Give the tracing for each algorithm by considering array demonstrating best case(if exists and worst-case separately. Write a Java program to implement this task by using separate functions wherever necessary. submit a neat report containing all the above(algorithm time complexity+ tracing +Program).

Problem Description (D): write a single program to compare between insertion sort and selection sort. For a given input array, write separate functions to implement insertion sort and selection sort algorithms and perform the below tasks: 1. The program should output number of comparisons and data movements made by each algorithm 2. The program should show intermediate steps (arrays) of the sorting process by each algorithm. 3. The program should have a mechanism to ask the user to "To Continue/auit" the program. suppose if user inputs 1, the program should re-run from the beginning asking for another run on a different input. If user inputs 0, the program should stop. Give the tracing for each algorithm by considering array demonstrating best case (if exists) and worst-case separately. write a Java program to implement this task by using separate functions wherever necessary. submit a neat report containing all the above (algorithm time complexity+ tracing +Program).

Explanation / Answer

package sample;

import java.util.Scanner;

public class SortMethods {
  
   public static void insertionSort(int arr[])
   {
       int n = arr.length;
       int count =0; //number of comparisons
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
  
count++;
}
arr[j+1] = key;
System.out.println("Array after iteration " + i);
printArray(arr);
}
  
System.out.println("Total number of comparisons in InsertionSort : "+ count);
   }
  
   public static void selectionSort(int arr[])
   {
       int n = arr.length;
       int count =0; //number of comparisons
   // 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;
  
   System.out.println("Array after iteration " + (i+1));
   printArray(arr);
   count++;
   }
   System.out.println("Total number of comparisons in selectionSort : "+ count);
   }
  
   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 N;
       Scanner sc = new Scanner(System.in);
       while(true)
       {
           System.out.println("Please enter number of element N");
           N = sc.nextInt();
          
           int arr[] = new int[N];
           System.out.println("Enter N array elements");
           for(int i=0;i<N;i++)
           {
               int data = sc.nextInt();
               arr[i] = data;
           }
           int arr1[] = arr;
           int arr2[] = arr;
          
           System.out.println("Before sorting array is: ");
           printArray(arr);
           insertionSort(arr);
           selectionSort(arr);
          
           int choice;
           System.out.println("To continue/Quit ");
           //enter 1 to continue or enter 0 to Quit
          
           choice = sc.nextInt();
           if(choice == 0)
               break;
           else
               continue;
       }
   }

}

//Output:

Please enter number of element N
5
Enter N array elements
4 2 6 1 7
Before sorting array is:
4 2 6 1 7
Array after iteration 1
2 4 6 1 7
Array after iteration 2
2 4 6 1 7
Array after iteration 3
1 2 4 6 7
Array after iteration 4
1 2 4 6 7
Total number of comparisons in InsertionSort : 4
Array after iteration 1
1 2 4 6 7
Array after iteration 2
1 2 4 6 7
Array after iteration 3
1 2 4 6 7
Array after iteration 4
1 2 4 6 7
Total number of comparisons in selectionSort : 4
To continue/Quit
1
Please enter number of element N
4
Enter N array elements
11 9 161 90
Before sorting array is:
11 9 161 90
Array after iteration 1
9 11 161 90
Array after iteration 2
9 11 161 90
Array after iteration 3
9 11 90 161
Total number of comparisons in InsertionSort : 2
Array after iteration 1
9 11 90 161
Array after iteration 2
9 11 90 161
Array after iteration 3
9 11 90 161
Total number of comparisons in selectionSort : 3
To continue/Quit
0

Time complexity:

Insertion Sort : O(N*N)

selection Sort : O(N*N)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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