Problem Description(D) Write a single program to compare between insertion sort
ID: 3832108 • Letter: P
Question
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/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).
Explanation / Answer
PROGRAM CODE:
package sort;
import java.util.Scanner;
public class SortComparator {
public static void printArray(int array[])
{
for(int i=0; i<array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println(" ");
}
public static void insertionSort(int array[])
{
int n = array.length, comparisons = 0;
System.out.println(" Insertion Sort: ");
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
comparisons++;
array [i+1] = array [i];
i--;
}
System.out.print("Intermediate array: ");
printArray(array);
array[i+1] = key;
}
System.out.println("Number of comparisons: " + comparisons);
System.out.println("Final array: ");
printArray(array);
System.out.println("------------------------------- ");
}
public static void selectionSort(int arr[])
{
int comparisons = 0;
System.out.println("Selection Sort: ");
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
comparisons++;
index = j;//searching for lowest index
}
}
System.out.print("Intermediate array: ");
printArray(arr);
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
System.out.println("Number of comparisons: " + comparisons);
System.out.println("Final array: ");
printArray(arr);
System.out.println("------------------------------- ");
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int choice = 1;
while(choice == 1)
{
System.out.print("Enter the number of elements in the array: ");
int length;
length = keyboard.nextInt();
int array[] = new int[length];
for(int i=0; i<length; i++)
{
System.out.print("Enter the element " + (i+1) + ": ");
array[i] = keyboard.nextInt();
}
insertionSort(array);
selectionSort(array);
System.out.println("Do you want to continue? 1 - continue 0 - exit Enter your choice: ");
choice = keyboard.nextInt();
}
}
}
OUTPUT:
Enter the number of elements in the array: 5
Enter the element 1: 22
Enter the element 2: 66
Enter the element 3: 11
Enter the element 4: 23
Enter the element 5: 98
Insertion Sort:
Intermediate array: 22 66 11 23 98
Intermediate array: 22 22 66 23 98
Intermediate array: 11 22 66 66 98
Intermediate array: 11 22 23 66 98
Number of comparisons: 3
Final array:
11 22 23 66 98
-------------------------------
Selection Sort:
Intermediate array: 11 22 23 66 98
Intermediate array: 11 22 23 66 98
Intermediate array: 11 22 23 66 98
Intermediate array: 11 22 23 66 98
Number of comparisons: 0
Final array:
11 22 23 66 98
-------------------------------
Do you want to continue?
1 - continue
0 - exit
Enter your choice:
1
Enter the number of elements in the array: 8
Enter the element 1: 43
Enter the element 2: 67
Enter the element 3: 21
Enter the element 4: 11
Enter the element 5: 10
Enter the element 6: 9
Enter the element 7: 54
Enter the element 8: 32
Insertion Sort:
Intermediate array: 43 67 21 11 10 9 54 32
Intermediate array: 43 43 67 11 10 9 54 32
Intermediate array: 21 21 43 67 10 9 54 32
Intermediate array: 11 11 21 43 67 9 54 32
Intermediate array: 10 10 11 21 43 67 54 32
Intermediate array: 9 10 11 21 43 67 67 32
Intermediate array: 9 10 11 21 43 43 54 67
Number of comparisons: 18
Final array:
9 10 11 21 32 43 54 67
-------------------------------
Selection Sort:
Intermediate array: 9 10 11 21 32 43 54 67
Intermediate array: 9 10 11 21 32 43 54 67
Intermediate array: 9 10 11 21 32 43 54 67
Intermediate array: 9 10 11 21 32 43 54 67
Intermediate array: 9 10 11 21 32 43 54 67
Intermediate array: 9 10 11 21 32 43 54 67
Intermediate array: 9 10 11 21 32 43 54 67
Number of comparisons: 0
Final array:
9 10 11 21 32 43 54 67
-------------------------------
Do you want to continue?
1 - continue
0 - exit
Enter your choice:
0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.