Brk - 7 months ago 36
Java Question

# Insertion Sort from Right to Left

I am trying to learn Insertion Sort in Java but I have a problem. I learned the insertion sort in ascending order. Now, I need to do it in descending order but I have to start sorting the array from right to left.

``````public class InsertionSort {

public static void sort(Comparable[] a) { // Sort a[] into increasing order.
int N = a.length;
for (int i = 1; i < N; i++) { // Insert a[i] among a[i-1], a[i-2],a[i-3]... ..
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}
}

private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
``````

}

The code which is above sorts the array from left to right in ascending order(1,2,3,4,..).

I need to change it in descending order but sorts from right to left(5,4,3,2..).
I change the code and tried this:

``````    public static void sort(Comparable[] a) { // Sort a[] into increasing order.
int N = a.length;
for (int i = N-1; i>=0; i--) { // Insert a[i] among a[i-1], a[i-2],
// a[i-3]... ..
for (int j = i; j >= 1 && less(a[j-1], a[j]); j++)
exch(a, j, j-1);
}
}
``````

I changed the sort method several times but I got errors..

here, I also tested it, try out:

``````    public class InsertionSort {
public static void main(String[] args) {
Comparable[] a = new Comparable[]{5,6,12,1,3,15,4,0,9};
sort(a);
for (int i = 1 ; i < a.length; i++)
assert a[i].compareTo(a[i-1]) >= 0;
System.out.println("sort is correct");
}

public static void sort(Comparable[] a) { // Sort a[] into         increasing order.
int N = a.length;
for (int i = N - 1; i > 0; i--) { // Insert a[i] among         a[i-1], a[i-2],a[i-3]... ..
for (int j = i; j < N && less(a[j - 1], a[j]); j++)
exch(a, j, j - 1);
}
}

private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

private static boolean less(Comparable v, Comparable w)                 {
return v.compareTo(w) < 0;
}

}
``````
Source (Stackoverflow)