I can't sort out Insertion Sort!

[melystar]

Hello, I'm a newbie to C. I'm trying to understand a source file about insertion sort and shell's sort, but when I try to run the programme on Microsoft VS C++ expressed edition, it always comes out with this error message!

sort_main.obj : error LNK2019: unresolved external symbol _insertion_sort referenced in function _main
C:\Documents and Settings\melystar\My Documents\Visual Studio 2008\Projects\sorting\Debug\sorting.exe : fatal error LNK1120: 1 unresolved externals

I have no idea what it means, could someone please explain to me?

[VernonDozier]

Does it compile on another compiler? Could be some specific option in Visual C++ that needs to be changed in the linker or whatever. Hard to say. Or it could be in the code itself. Posting the code would help. People (i.e. me) can try to compile it and see if they get the same results.

[melystar]

#define _CRT_SECURE_NO_DEPRECATE

#include <stdio.h>
#include <stdlib.h>

#include "sort.h"


int main(void)
{
  int n;
  int *A = NULL, *A_copy = NULL;
  int sort_ascending, random;
  work_counter work;

  int i;

  /* Read in the sequence length */
  printf("Enter the length of the sequence: ");
  scanf("%d", &n);

  /* Allocate memory for arrays */
  A = (int *)malloc(n*sizeof(int));
  A_copy = (int *)malloc(n*sizeof(int));
  if ((A == NULL) || (A_copy == NULL))
  {
    printf("Not enough memory available\n");
    exit(EXIT_FAILURE);
  }
  
  /* Determine sequence type */
  printf("Enter 0 for a given seqence, 1 for a random sequence: ");
  scanf("%d", &random);

  if (random)
  {
    /* Generate random sequence */
    printf("Generating random integers in range [%d,%d]\n", 0, RAND_MAX);
    for (i = 0; i < n; i++)
    {
      A[i] = rand();
      A_copy[i] = A[i];
    }
  }
  else
  {
    /* Read in given sequence */
    printf("Enter given sequence\n");
    for (i = 0; i < n; i++)
    {
      scanf("%d", &(A[i]));
      A_copy[i] = A[i];
    }
  }

  /* Determine sequence ordering */
  printf("Enter 0 to sort descending, 1 to sort ascending: ");
  scanf("%d", &sort_ascending);

  /* Output original sequence */
  printf("*** Original sequence\n");
  printf("A = [ ");
  for(i = 0; i < n; i++)
    printf("%d ",A[i]);
  printf("]\n");
  printf("\n");
  
  /* Perform insertion sort */
  printf("*** Insertion sort\n");

  work.comparisons = 0;
  work.swaps = 0;

  insertion_sort(n,A,1,sort_ascending,&work);
  
  printf("A = [ ");
  for(i = 0; i < n; i++)
    printf("%d ",A[i]);
  printf("]\n");
  printf("comparisons = %d, swaps = %d\n", work.comparisons, work.swaps);
  printf("\n");

  /* Perform Shells sort */

  /* Free allocated memory */
  free(A); A = NULL;
  free(A_copy); A_copy = NULL;

  return 0;
}

Thanks very much!

[melystar]

And this is the sort.h file:

/* Create an operations counter variable type */
struct work_counter_struct 
{
  int comparisons;
  int swaps;
};

typedef struct work_counter_struct work_counter;


/*
 * Shells sort routine
 */
void shells_sort(int n, int *A, int sort_ascending, work_counter *work);


/*
 * Insertion sort routine
 */
void insertion_sort(int n, int *A, int inc, int sort_ascending, work_counter *work);

[VernonDozier]

Do you have the implementation code for the functions in sort.h? It needs that file too in order to compile.

[melystar]

It says on the exercise that I have to make a sort.c file that implements the insertion sort algorithm. So does the new sort.c have anything to do with the sort_main.c file? The sort_main.c file is the big block of code that I typed out.

[VernonDozier]

Well there's your problem. If sort.c doesn't exist yet, then you can't call these two functions yet:

void shells_sort(int n, int *A, int sort_ascending, work_counter *work);

and

void insertion_sort(int n, int *A, int inc, int sort_ascending, work_counter *work);

You declare these functions in your sort.h file, which is fine, but that's not enough to allow you to call them from sort_main.c, as you do here:

insertion_sort(n,A,1,sort_ascending,&work);

No such function exists yet. All your sort.h file does is alert the compiler that such a function may be out there so that it doesn't just give an error when it sees that call in sort_main.c. It'll still give you an error if you call it without the actual function existing. Add this file to your project in Visual C++:

// Filename : sort.c
#include "sort.h"


void shells_sort(int n, int *A, int sort_ascending, work_counter *work)
{
}


void insertion_sort(int n, int *A, int inc, int sort_ascending, work_counter *work)
{
}

See if that makes the project compile. They are empty functions that do nothing, but they would at least exist now, so hopefully that'll be enough to make the project at least compile.

[melystar]

Oh! That clears up a lot of things ^^ Could you have a look at this code that I wrote?

#include <stdio.h>

void insertion_sort(int A[6], int n)
{
	int i, j, key;
	
	for(j = 2; j<n; j++)
	{
		key = A[j];
		i = j-1;
		while((i > 0) && (A[i] > key));
		{
			A[i + 1] = A[i];
			i=i-1;
		}
			A[i+1]=key;
	}

	for(key = 0; key < n; key++)
{
	printf("%d", A[key]);

}
	}

int main(void)
{
	int A[6]={5,2,4,6,1,3};
	int n=6;

	insertion_sort(A,n);
}

It compiles but does not print anything, even though I did include a print statement.

[Narue]

>while((i > 0) && (A > key));
Remove the semicolon. What you have right now is a loop that either doesn't run at all, or runs forever. Here's the equivalent loop with braces:

while((i > 0) && (A[i] > key))
{
    ;
}

Also, your algorithm is incorrect, but I'll give you a chance to fix it on your own first.

[melystar]

Thanks, I managed to figure it out before I went back on the forums. Sorry if I broke any rules. I thought that if I did include the code which I tried, it wouldn't be considered cheating...