Search code examples
javaalgorithminsertion-sort

My Insertion sort algorithm leaves larger number unsorted

I'm trying to sort the following list (which gets inserted to the a array): 10 9 8 7 6 5 4 3 2 1 After the below java code executes I get the following (not sure why the largest number is still unsorted, thanks in advance for any help you can provide): 10 1 2 3 4 5 6 7 8 9

I'm basically implementing the java code from the following pseudocode from a text book:

procedure insertionsort(a1, a2, ...an: real numbers with n>=2)
for j:=2 to n
begin
i:=1
while a[j]>a[i]
  i=:i+1

temp:=a[j]

for k:=0 to j - i - 1
 a[j-k] := a[j-k-1]

a[i]:=temp
end

java code:

int k, j,i;  
long temp;

for(j=2; j<nElems; j++)   
{
   i=1;  

   //also tried while(a[j]>=a[i]) 
   while(a[j]>a[i]) 
       i = i +1;         

   temp = a[j];            
   for(k=0; k<=(j-i-1);k++)  
         a[j-k] = a[j-k-1];

   a[i] = temp;                 
}// end for
Solution

  • The problem is that the pseudocode array is 1-based, while Java arrays are 0-based.

    Just change 

    for (j=2; j<nElems; j++) {
    i=1;
    // more code

    to

    for (j=1; j<nElems; j++) {
    i=0;
    // more code