Sorry if its a basic question...
I am just trying to learn more on algorithms...
I wrote a simple code to perform insertion sort in ascending order, but for some reason I couldn't make it work to perform sort in descending order.
I tried changing the comparison key (while (i > 0 && a[i] > key) to (i > 0 && a[i] < key)).. it seems to work partially but the first element is not getting sorted, I get the below results..Can someone let me know where I am wrong?
1 11 10 9 5 4 3 2
public class InsertionSort {
public static void main(String args[]) {
int[] a = { 1,10,11,5, 9, 3, 2, 4 };
// Loop through the entire array length. Consider you already have one
// element in array, start comparing with
// first element
for (int j = 1; j < a.length; j++) {
// Get the key (The value that needs to be compared with existing
// values.
int key = a[j];
// Get the array index for comparison, we need to compare with all
// other elements in the array with
// key
int i = j - 1;
// While i > 0 and when key is less than the value in the array
// shift the value and insert
// the value appropriately.
//System.out.println(j);
while (i > 0 && a[i] < key) {
a[i + 1] = a[i];
i = i - 1;
a[i + 1] = key;
}
}
for (int k = 0; k < a.length; k++) {
System.out.println(a[k]);
}
}
}
You're never touching a[0]
in
while (i > 0 && a[i] < key) {
so it isn't sorted into its due place. Use >=
instead of >
:
while (i >= 0 && a[i] < key) {
The same problem would occur when sorting in ascending order.