CODEWITHSUNDEEP
javaalgorithminsertion-sort
Curlylids
Curlylids

Reputation: 3

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

Upvotes: 0

Views: 113

Answers (2)

UrsinusTheStrong
UrsinusTheStrong

Reputation: 1209

In the pseudocode, the array index seems to start from "1" whereas, in Java, array index starts from "0".

Change the code to:

public class InsertionSort{
    public static void main(String[] args) {

        int k,j,i,n=5;  
        long a[]={1025,3689,125,12,254},temp;


        for(j=1; j<n; j++) // instead of j=2
        {
            i=0; // instead of i=1
            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

        for(long x:a){
            System.out.print(x+" ");
        }

    }

}

Output: 12 125 254 1025 3689

Upvotes: 2

ThreeFx
ThreeFx

Reputation: 7360

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

Upvotes: 0

Related Questions