Question

Implement the static method sort() in IndirectSort.java that indirectly sorts a[] using insertion sort, ie, not by rearranging a[], but by returning an array perm[] such that perm[i] is the index of the ith smallest entry in a[].

the object returned in the method is a comparable item, so i cant exactly copy it. I've included the code give to me to complete.

Answer 1

Answer:

// Java program to implement indirect sort

public class IndirectSort {

private static boolean less(Comparable v, Comparable w)

{

return(v.compareTo(w) < 0);

}

private static void exch(int[] a, int i, int j)

{

int swap = a[i];

a[i] = a[j];

a[j] = swap;

}

// Indirectly sorts a[] using insertion sort, ie, not by rearranging a[],

// but by returning an array perm[] such that perm[i] is the index of

// the ith smallest entry in a[]

public static int[] indexSort(Comparable[] a)

{

int perm[] = new int[a.length];

for(int i=0;i<a.length;i++)

perm[i] = i;

int i,j,key;

for(i=1;i<perm.length;i++)

{

j=i-1;

key = perm[i];

while(j>=0 && less(a[key],a[perm[j]]))

{

perm[j+1] = perm[j];

j--;

}

perm[j+1] = key;

}

return perm;

}

public static void main(String[] args) {

String[] a = {"I","N","D","I","R","E","C","T","I","N","S","E","R","T","I","O","N","S","O","R","T","E","X","A","M","P","L","E"};

int perm[]= indexSort(a);

int i;

System.out.println(" Original Data : ");

for(i=0;i<a.length-1;i++)

System.out.print(a[i]+" ");

System.out.println(a[i]);

System.out.println(" Sorted Data : ");

for(i=0;i<perm.length-1;i++)

System.out.print(a[perm[i]]+" ");

System.out.println(a[perm[i]]);

}

}

//end of program