CODEWITHSUNDEEP
csortinginsertion-sort
marcello
marcello

Reputation: 21

Insertion Sort (descending order) -- what am I missing here?

So, I'm struggling pretty hard on this insertion sort algorithm, I can't understand why I'm getting this output. I've gone through it on paper and it works there as I step through it...what is going on?

int main(int argc, char * argv[]){

   int arrayIn[5];


   /* Insertion func */

   printf("==============================\n");

   for(int k=0; k<5; k++){
      arrayIn[k] = k + 1;
   }

   for(int y = 0; y < 5; y++){
      printf("array[%d]: %d \n", y, arrayIn[y]);
   }

   //insertion

   for (int j = 1; j < 5 - 1; j++) {
      int i = j - 1;
      int temp = arrayIn[j];

      while (i >= 0 && arrayIn[i] < arrayIn[j] /* Aj < Ai */) {
         arrayIn[i+1] = arrayIn[i];
         i--;
      }
      arrayIn[i+1] = temp;

   }

   for(int p = 0; p < 5; p++){
      printf("array[%d]: %d \n", p, arrayIn[p]);
   }   



   return(0);
}

This is the output I'm getting:

Before insertion sort:

array[0]: 1 
array[1]: 2 
array[2]: 3 
array[3]: 4 
array[4]: 5

After insertion sort:

array[0]: 2 
array[1]: 3 
array[2]: 4 
array[3]: 1 
array[4]: 5

Upvotes: 1

Views: 4249

Answers (1)

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58271

While condition is wrong: 

while (i >= 0 && arrayIn[i] < arrayIn[j])

Should be:

while (i >= 0 && arrayIn[i] < temp)

Because arrayIn[j] is nothing but arrayIn[i + 1] in first iteration in while loop that can be over-written in arrayIn[i+1] = arrayIn[i]; in while.

In insertion sort you insert a value in sorted array, In outer loop you reads arrayIn[j] in temp. Now you are to insert temp at sorted position, and for every arrayIn[i] that is smaller than temp a shift needed arrayIn[i+1] = arrayIn[i]; At first time you may write to arrayIn[j] = arrayIn[i]; if arrayIn[j] > arrayIn[i]; because j = i + 1.

Edit, from @M Oehm: Yours outer for loop run just for i = 1 to 3 and doesn't insert arrayIn[4] to sorted position, change j < 5 - 1; to j < 5.

Upvotes: 2

Related Questions