Member Avatar for yongj

So with my program I'm trying to count the number of operations it takes to perform a insertion sort/quick sort. And because functions are calling other functions from inherited classes, it gets a bit confusing as to where I can place the operation to increment the number of operations. Right now my code is trying to compile but keeps getting the error saying that void InsertionSort::insertionsort(long*const, int) is being referenced someplace else--and it is because another function returns numops without going through the insertionsort function.

Here's what I mean..

Header file:

#ifndef INSERTIONSORT_H
#define INSERTIONSORT_H

#include "SortData.h"

class InsertionSort : public SortData
{
public:
	InsertionSort(int max=100);
	~InsertionSort(void);
	_int64 sort();

private:
	_int64 numops;
	void insertionsort(long theArray[], int n);
};

#endif

Implementation file:

_int64 InsertionSort::sort()
{
	numops = 0;
	insertionsort(theData, maxSize);
	return(numops);
}

void insertionsort(long theArray[], int n)
{
	int i, j, key;
	_int64 numops = 0;
    for(j = 1; j < n; j++)    
    {
		key = theArray[j];
        for(i = j - 1; (i >= 0) && (theArray[i] < key); i--)   
        {
			theArray[i+1] = theArray[i];
			numops =+ 1;
        }
		
		theArray[i+1] = key;    
     }
}

And the main.cpp

void test(SortData& ad, bool print=false)
{
	ad.randomize();
	if(print)
	{
		cout << "Unsorted Dataset size(" << ad.size() << "):" << endl;
		ad.printSome();
	}

	_int64 num = ad.sort();
	if(print)
	{
		cout << "Sorted Dataset size(" << ad.size() << "):" << endl;
		ad.printSome();
	}

	cout << "Dataset Size= " << setw(8) << ad.size();
	cout << " Num Ops = "<< num << endl;
}

Here's the error code:

Error	1	error LNK2019: unresolved external symbol "private: void __thiscall InsertionSort::insertionsort(long * const,int)" (?insertionsort@InsertionSort@@AAEXQAJH@Z) referenced in function "public: virtual __int64 __thiscall InsertionSort::sort(void)" (?sort@InsertionSort@@UAE_JXZ)	C:\Users\Joseph\documents\visual studio 2010\Projects\CSC2431 Sorting Efficiency\CSC2431 Sorting Efficiency\InsertionSort.obj	CSC2431 Sorting Efficiency
Error	2	error LNK2019: unresolved external symbol "private: void __thiscall QuickSort::quicksort(long * const,int)" (?quicksort@QuickSort@@AAEXQAJH@Z) referenced in function "public: virtual __int64 __thiscall QuickSort::sort(void)" (?sort@QuickSort@@UAE_JXZ)	C:\Users\Joseph\documents\visual studio 2010\Projects\CSC2431 Sorting Efficiency\CSC2431 Sorting Efficiency\QuickSort.obj	CSC2431 Sorting Efficiency

Can someone help me please? This is the last thing that's keeping the code from compiling fully. Argh...

Thanks all!!

J

  • 2 Contributors
  • 1 Reply
  • 287 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by mitrmkar

Dani AI

Generated

As pointed out, the linker error LNK2019 means the class-declared methods were never defined with the correct class scope/signature. In 's example the insertion routine is implemented as a free function (no InsertionSort::), so the linker cannot find InsertionSort::insertionsort(...). The QuickSort complaint is the same kind of problem for QuickSort::quicksort(...).

There are a few additional bugs that will still give wrong results even after fixing the linker error:

  • insertionsort declares a local _int64 numops which hides the class member; the member returned by sort() stays 0.
  • numops =+ 1; is not increment; use numops += 1; or ++numops;. (numops =+ 1 assigns +1.)
  • The inner comparison appears reversed for a normal ascending insertion sort (should compare theArray[i] > key).
  • key should match the array element type (long), and index types should be appropriate (int or size_t).

A minimal corrected implementation looks like this:

void InsertionSort::insertionsort(long theArray[], int n)
{
    long key;
    for (int j = 1; j < n; ++j) {
        key = theArray[j];
        int i = j - 1;
        while (i >= 0 && theArray[i] > key) {
            theArray[i + 1] = theArray[i];
            ++numops;   // increment class member set to 0 in sort()
            --i;
        }
        theArray[i + 1] = key;
    }
}

Checklist to finish debugging:

  • Make sure the implementation signatures match the header exactly (including consts).
  • Remove the local numops inside the sort routine so the member is updated.
  • Fix numops =+ 1 to ++numops or numops += 1.
  • Verify all .cpp files are added to the Visual Studio project and are being compiled/linked.
  • Apply the same scope/signature fixes to QuickSort.

These fixes should resolve the linker errors and produce a correct operation count.

Member Avatar for mitrmkar

In your implementation file you have forgotten

void InsertionSort::insertionsort(long theArray[], int n)
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.