JAVA: fill in the rest for insertion sort: based on the follwoing: INSERTION-SOR
ID: 3890212 • Letter: J
Question
JAVA: fill in the rest for insertion sort:
based on the follwoing:
INSERTION-SORT.A/
1 for j D 2 to A:length
2 keyDAŒj
3 // Insert AŒj into the sorted sequence AŒ1 : : j 1 .
4 iDj 1
5 whilei >0andAŒi >key
6 AŒi C 1 D AŒi
7 iDi 1
8 AŒiC1 Dkey
public class Sort {
public static int[] insertion_sort (int[] array) {
return array;
/*
* fill in your program
*/
}
public static int[] merge_sort (int[] array, int p, int r) {
/*
* fill in your program
*/
int q;
if (p < r){
q = (p + r)/2;
Sort.merge_sort(array, p, q);
Sort.merge_sort(array, q+1, r);
array = Sort.merge(array, p, q, r);
}
return array;
}
public static int[] merge (int[] array, int p, int q, int r) {
/*
* fill in your program
*/
int n1, n2, i, j, k;
int[] L, R;
n1 = q - p +1;
n2 = r - q;
L = new int[n1+1];
R = new int[n2+1];
for (i = 0; i < n1; i++)
L[i] = array[p+i];
for (j = 0; j < n2; j++)
R[j] = array[q+1+j];
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
i = 0;
j = 0;
for (k = p; k <= r; k++) {
if (L[i] <= R[j]){
i++;
}
else {
array [k] = R[j];
j++;
}
}
return array;
}
/*
* n: the size of the output array
*/
public static int[] generate_random_array (int n) {
List list;
int[] array;
list = new ArrayList ();
for (int i = 1; i <= n; i++)
list.add(new Integer(i));
Collections.shuffle(list, new Random(System.currentTimeMillis()));
array = new int[n];
for (int i = 0; i < n; i++)
array[i] = list.get(i).intValue();
return array;
}
/*
* Input: an integer array
* Output: true if the array is acsendingly sorted, otherwise return false
*/
public static boolean check_sorted (int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i-1] > array[i])
return false;
}
return true;
}
public static void print_array (int[] array) {
for (int i = 0; i < array.length; i++)
System.out.print(array[i] + ", ");
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Insertion sort starts ------------------");
for (int n = 10; n <= 100000; n=n*2) {
int[] array = Sort.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort.insertion_sort(array);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Insertion sort ends ------------------");
System.out.println("Merge sort starts ------------------");
for (int n = 10; n <= 100000; n=n*2) {
int[] array = Sort.generate_random_array(n);
long t1 = System.currentTimeMillis();
array = Sort.merge_sort(array, 0, n-1);
long t2 = System.currentTimeMillis();
long t = t2 - t1;
boolean flag = Sort.check_sorted(array);
System.out.println(n + "," + t + "," + flag);
}
System.out.println("Merge sort ends ------------------");
}
}
Explanation / Answer
Basic steps to be follwed in Insertion sort:
1. Insertion sort is simple to implement
2. Insertion sort is good for small size elements but not for large elements.
3.Insertion sort iterates though out the array and iterates are equal to array size.
4. Each iteration, insertion sort removes one element from the input data and finds the location it belongs within the sorted list, and inserts it there.
5.It repeats the same until end of the input array.
6. Sorting typically done in place by comparing the each element and at every position and check there is any value largest against it.
7.If larger element found it leaves the element in place and moves to the next and incase of smaller it finds the correct position within the sorted list, and place it there.
Worst Case Performance: O(n2) comparisons
Best Case Performance: O(n) comparisons
Average Case Performance: O(n2) comparisons
Worst Case space complexity: O(n) total and O(1) auxiliary
Code for insertion sort is :
public static int[] insertion_sort (int[] array) {
for (int i = 1; i < n; i++){
int j = i;
int B = array[i];
while ((j > 0) && (array[j-1] > B)){
array[j] = array[j-1];
j--;
}
array[j] = B;
}
return array;
}
In the given code array elements taken as random numbers.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.