Write a program that takes in any user defined number values and then performs i

Question

Write a program that takes in any user defined number values and then performs insertion sort resulting in an array of values in ascending order.

First the user must input how many values they are entering

Next the user enters that many values, which populates an array of the size previously entered.

Using TWO arrays then perform insertion sort

The first array stays unsorted

The second array is sorted

Pseudo-code for insertion sort

// a is the first array

for(index = 0; index < a.lenght-1; index++)

      put the value of index a[index] into the second array in the correctly sorted position

      (IE the values at a lower index are less than the value. The values at a higher index are greater than the value.)

When inserting a number in the middle of the array all other numbers ahead of it must be shifted forward

HINT: Start from the back and pull the values forward

Example Dialog:

Welcome to the insertion sorter

Please enter the number of values you would like to sort

6

Please enter the number at 0

5

Please enter the number at 1

6

Please enter the number at 2

8

Please enter the number at 3

7

Please enter the number at 4

4

Please enter the number at 5

1

The unsorted array is

5 6 8 7 4 1

The sorted array is

1 4 5 6 7 8

Done!

Explanation / Answer

package mani;

import java.util.Scanner;

public class MyInsertionSort {
   int[] input ;
   int[] duplicate;
   public MyInsertionSort(int n){
       input=new int[n];
       duplicate=new int[n];
   }
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
  
System.out.println("Welcome to the insertion sorter");
System.out.println("Please enter the number of values you would like to sort");
int n=scan.nextInt();
MyInsertionSort my=new MyInsertionSort(n);
my.arrayFill();
}
  
private void arrayFill() {
   Scanner scan=new Scanner(System.in);
for (int i = 0; i < input.length; i++) {
System.out.println("Please enter the number at "+i);
input[i]=scan.nextInt();
}
System.out.println(" ");
System.out.println("The unsorted array:");
for(int i=0;i<input.length;i++){
   System.out.print(input[i]+" ");
}
  
duplicate=input.clone();
insertionSort();
System.out.println(" The sorted array:");
for(int i=0;i<duplicate.length;i++){
   System.out.print(duplicate[i]+" ");
}
}

public void insertionSort() {
int n = duplicate.length;
for (int j = 1; j < n; j++) {
int key = duplicate[j];
int i = j-1;
while ( (i > -1) && ( duplicate [i] > key ) ) {
duplicate [i+1] = duplicate [i];
i--;
}
duplicate[i+1] = key;
  
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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