Vfrdtyky

Basically, I was wondering if there are any possible logic errors that could occur when implementing the following code to perform an insertion sort. I noticed that some examples use a while loop with the logical AND operator, but I think I can achieve the same output by using a flag to monitor whether any of the values in the sorted list are smaller than the the current index of the unsorted list, and by storing the position of that smaller value.

#include<stdio.h>

void insertion(int size, int[*]);

int main()

{

  int size;

  printf("Size of Array: ");

  scanf("%d",&size);

  int ary[size];

  for(int i=0; i<size; i++)

  scanf("%d",&ary[i]);

  insertion(size, ary);

  return 0;

}

 void insertion(int size, int A[size])

 {

   int value;

   int hole;

   int flag;



   for(int i=1; i<size; i++)

     {

       value = A[i];//the value of the current index of the unsorted list 

                    //gets stored in variable named value

       flag = 0;

           for(int j=i-1; j>=0; j--)

              {

                 if(A[j]>value)

                    {

                       flag = 1;

                       hole = j; //index position where value will be 

                                 //inserted into

                       A[j+1] = A[j];

                    }

              }

          if(flag) //ensures that insertion occurs only when one of the 

                   //sorted elements is less than value

     A[hole] = value;

    }



  for(int i=0; i<size; i++)

  printf("%d ",A[i]);

}

`

This following method is the alternate variation that uses a while loop instead of a flag:

void unshuffle( int size, int* A )

{

int value;

int position;



for( int i=1; i<size; i++ )

    {

    value = A[i];

    position = i;



    while( A[position-1]>value && position>0 )

        {

        A[position] = A[position-1];

        position--;

        }

    A[position] = value;

    }



}

Is this the preferred method for writing an insertion sort in terms of efficiency?

You are getting less efficient with your approach; consider following variant of your algorithm:

for(int j=i-1; j>=0; j--)

{

    if(A[j] > value)

    {

        A[j+1] = A[j];

    }

    else

    {

        A[j+1] = value; // worst that could happen: self asignment;

                        // still less costly than another `if`!



        break;          // you're in the sorted part of the array, so all other

                        // values are smaller or equal as well -> can exit!

    }

}

Now you don't need the flag/hole any more, but more important, you don't needlessly iterate over the already sorted smaller part any more.

The same you'd achieve with the double condition in the while loop you started from...

Actually, there's an error in, if the current element is smaller than all already sorted ones, the else clause is never entered, so the element won't be inserted at first location. Fix is easy, though:

int j;

for(j = i-1; j >= 0; j--)

{

    if(A[j] > value)

    {

        A[j+1] = A[j];

    }

    else

    {

        break;

    }

}

A[j+1] = value; // (still self-assignment possible)

                // if j got -1: insert at 0, so fine

Now we got even closer to the original while loop...

Still you are trying to optimise an algorithm that is well known for its inefficiency (average(!) runtime of O(n²)), I don't consider it worth to care for such one that much, better switch to quick-sort right from start (O(n log(n)) average runtime), heap-sort (with maximum O(n log(n)) runtime, but worse constants than quicksort) or intro-sort (hybrid of first two, standard sorting algorithm of C++ std::sort in most implementations).