11 Replies - 9517 Views - Last Post: 16 July 2010 - 11:25 PM Rate Topic: -----

#1 Guest_Dc*


Reputation:

insertion sort

Posted 16 July 2010 - 12:39 PM

Can anyone tell me if i am on the right track.
void insertionSort(string data[],int n)
{
//
// TODO: Implement the Insertion Sort aglorightm
//
// Hints:
//
// (1) You will need a tmp variable declared as type string.
//
// (2) Use the strcmp() function in your for-loop when comparing the tmp string 
//     and an item in the data array.
//
// You will need to call strcmp() with the c_str()method. For example replace the call for 
//     tmp < data[j-1] with the following: strcmp(tmp.c_str(), data[j-1].c_str()) < 0;
//
// See the example in the CompareString.zip archive for more details

*/

  for(int i=1; i<n; i++)
  {
	  i= j-1
		  tmp = data[i];
     while (j=i;j>0 && tmp < data[j-1]; j--)
		 data [j] = data[j-1];
		 data [j] = tmp;
  }
}

return;
}



This post has been edited by JackOfAllTrades: 16 July 2010 - 12:42 PM
Reason for edit:: Moved question out of code block.


Is This A Good Question/Topic? 0

Replies To: insertion sort

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6246
  • View blog
  • Posts: 24,014
  • Joined: 23-August 08

Re: insertion sort

Posted 16 July 2010 - 12:43 PM

We have a general sorting tutorial and one specifically for insertion sort. Feel free to check them out and see if they're helpful.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Dc*


Reputation:

Re: insertion sort

Posted 16 July 2010 - 12:56 PM

still need to know if the code I have in on the right track.
Was This Post Helpful? 0

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6246
  • View blog
  • Posts: 24,014
  • Joined: 23-August 08

Re: insertion sort

Posted 16 July 2010 - 01:06 PM

And I think if you put a little thought into it, you can come up with it on your own by reading those links. HINTS to get you started, there's no definition of j in your code, and I think your while loop's scope is incorrect.
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Dc*


Reputation:

Re: insertion sort

Posted 16 July 2010 - 01:09 PM

Ok thanks for the HINTS.
Was This Post Helpful? 0

#6 Guest_Dc*


Reputation:

Re: insertion sort

Posted 16 July 2010 - 01:54 PM

void insertionSort(string data[],int n)
int i,j,tmp;
  for(i=1; i<n; i++)
  {
	  int j= i-1;

	while (j>0 && data[j-1] > data[j])
	{
		tmp= data[j];
		 data[j] = data[j-1];
  		 data [j+1] = tmp;
		 j--;
	}
  }
return;
}

I am getting a error error C2440: '=' : cannot convert from 'std::string' to 'int'






Was This Post Helpful? 0

#7 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6246
  • View blog
  • Posts: 24,014
  • Joined: 23-August 08

Re: insertion sort

Posted 16 July 2010 - 01:56 PM

Try to understand what you're doing rather than just throwing code at it. The error tells you everything you need to know.

What datatype is data? What about data[j]? What about tmp?
Was This Post Helpful? 0
  • +
  • -

#8 Guest_Dc*


Reputation:

Re: insertion sort

Posted 16 July 2010 - 02:04 PM

thank you for your help. I know this may seem easy to you but I am having a hard time understand C++. data is declared a string so I will need to declare tmp the same?
Was This Post Helpful? 0

#9 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: insertion sort

Posted 16 July 2010 - 02:35 PM

View PostDc, on 16 July 2010 - 08:04 PM, said:

thank you for your help. I know this may seem easy to you but I am having a hard time understand C++. data is declared a string so I will need to declare tmp the same?


Yeah because you are assigning a string to tmp.
Was This Post Helpful? 0
  • +
  • -

#10 Guest_Dc*


Reputation:

Re: insertion sort

Posted 16 July 2010 - 03:45 PM

Ok I was looking over some notes and I have made some changes.

int i,j,least;
void insertionSort(string data[],int n)

{
for (int i=0, j; i < n; i++){
for (j = i + 1; j < n; j++)
if (data[j] < data[i])
least = j;
swap(data[least], data[i]);

if (strcmp(data[i].c_str(), data[j].c_str()) < 0)

return;
}
}
Was This Post Helpful? 0

#11 Guest_Dc*


Reputation:

Re: insertion sort

Posted 16 July 2010 - 03:47 PM

void insertionSort(string data[],int n)

{ 
   	   for (int i=0, j; i < n; i++){
		   for (j = i + 1; j < n; j++)
			   if (data[j] < data[i])
				   least = j;
		   swap(data[least], data[i]);

 if (strcmp(data[i].c_str(), data[j].c_str()) < 0)

return;
	   }
}



Was This Post Helpful? 0

#12 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 298
  • View blog
  • Posts: 1,839
  • Joined: 20-September 08

Re: insertion sort

Posted 16 July 2010 - 11:25 PM

View PostDc, on 16 July 2010 - 04:47 PM, said:

void insertionSort(string data[],int n)

{ 
   	   for (int i=0, j; i < n; i++){
		   for (j = i + 1; j < n; j++)
			   if (data[j] < data[i])
				   least = j;
		   swap(data[least], data[i]);

 if (strcmp(data[i].c_str(), data[j].c_str()) < 0)

return;
	   }
}


Looks like the rough beginnings of a selection sort ...

void selectionSort( char* data[], int n )
{
   int j;
   for( int i = 0; i < n-1; ++i )
   {
      int least = i; // initial value for least
      for( j = i + 1; j < n; ++j )
      {
			if( strcmp( data[j], data[least] ) < 0 )
				least = j; // update least
      }
      //swap( data[least], data[i] );
      if( least != i )
      {
         char* tmp = data[i];
         data[i] = data[least];
         data[least] = tmp;
      }
	}
}



If you want an insertion sort try these, for C strings ... or for C++ strings that use strcmp:

// C string array insert sorted ...
void isortCStrAry( char* data[], int size )
{
  int j;
  char* cmp; // cmp is a pointer to a C string

  for( int i = 1; i < size; ++i )
  {
    cmp = data[i]; // store pointer in cmp ...
	 j = i - 1;

    while( j >= 0 && strcmp( cmp, data[j] ) < 0 )
    {
      data[j + 1] = data[j]; // copy pointer up
		--j;
    }
	 data[j + 1] = cmp; // insert pointer ...
  }
}

// C++ string array insert sorted using strcmp
void isortCppStrAryStrCmp(string data[],int size)
{
  int j;
  char* cmp; // cmp is a pointer to a C string

  for( int i = 1; i < size; ++i )
  {
    cmp = (char*)data[i].c_str();//pointer in cmp
	 j = i - 1;

    while(j>=0 && strcmp(cmp,data[j].c_str())<0)
    {
      data[j + 1] = data[j]; // copy up
		--j;
    }
	 data[j + 1] = string(cmp); // insert
  }
}




Else ... try this:

template <class T >
void isortAry( T data[], int size )
{
  T cmp;
  int j;

  //array is traversed size-1 times ...
  for( int i = 1; i < size; ++i )
  {
    cmp = data[i]; //new compare value each pass
	 j = i - 1; //on each pass, j = last_index-1

   //compare new 'cmp' this pass with val's to left
    while( j >= 0 && cmp < data[j] )
    {
      data[j + 1] = data[j];//copy over right val
		--j; //get next index to left ...
    }
	 data[j + 1] = cmp; //insert this 'cmp', here
  }
}



called like this:

(for an array of type int)
isortAry<int>( a, sizeA );



(for an array of type string)
isortAry<string>( b, sizeB );


This post has been edited by David W: 17 July 2010 - 01:00 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1