1 for j = 2 to A. length 2 key = A[ j ] 3 // Insert A[ j ] into the sorted seque
ID: 3891073 • Letter: 1
Question
1 for j = 2 to A.length
2 key = A[ j ]
3 // Insert A[ j ] into the sorted sequence A[1 . . j - 1 ]
4 i = j - 1
5 while i > 0 and A[ i ] > key
6 A[ i + 1 ] = A[ i ]
7 i = i - 1
8 A[ i + 1 ] = key
Question: Using swap(x,y) to rewrite the Insertion sort Algorithm pseudo code listed above to reduce the number of assignments (=) performed in the inner loop. Assume that each swap(x,y) means 3 assignments (namely temp = x; x = y; y = temp). Then, compare the two versions of the insertion sort algorithm in terms of asymptotic complexity. Does the insertion sort with swap improve its performance, explain?
Write the pusedocode in java using Swap and explain how it imporves the perfomance.
Explanation / Answer
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Surya
*/
import java.util.Scanner;
/* Class InsertionSort */
public class InsertionSort
{
/* Insertion Sort function */
public static void swap(int a[],int x,int y)
{
int temp;
//2 assignment operations..
temp =a[x];
a[x]=a[y];
a[y]=temp;
}
public static void sort( int array[] )
{
int n = array.length;
int i, j, key;
for (i = 1; i< n; i++)
{
j = i;
key = array[i];
while (j > 0 && key < array[j-1])
{
swap(array,j,j-1);//calling swapping function..
j = j-1;
}
}
}
/* Main method */
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Insertion Sort ");
int n, i;
/* Accept number of elements */
System.out.println("Enter number of integer elements in ARRAY :");
n = scan.nextInt();
/* Create integer array on n elements */
int arr[] = new int[ n ];
/* Accept elements */
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/* Call method sort */
sort(arr);
/* Print sorted Array */
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
//the performance is same..
output:
run:
Insertion Sort
Enter number of integer elements in ARRAY :
5
Enter 5 integer elements
3
4
2
7
9
Elements after sorting
2 3 4 7 9
BUILD SUCCESSFUL (total time: 8 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.