Sorting Help

[Salchester]

I am currently creating a C++ program that sorts names; I need to move 4 names from the bottom of the list in memory to the top of the list in memory. There are 36 names altogether how do I do this.

Many Thanks

Unsorted example:

Jonathan
Jane
David
Kellie
Lucy
Jamie
Mark

Sorted example:

Kellie
Lucy
Jamie
Mark
Jonathan
Jane
David

[redhead]

Use std::string::compare() on a std::algorithm::sort() With the strings stored in a std::vector <std::string>

Wouldn't that be the easy way ??

[Salchester]

What other way could i do it?

[redhead]

From your example it looks like you just want to shift the bottom four names above all others, without paying attention to them beeing sortet at all, is that correct ??
Then just use something like a std::queue to store them in, and pop() size()-4 times followed by push()

[Salchester]

That's correct, but how would i go about writing this in old c++ as i know how to do it in this.

Then eventually i will convert it to using namespaces etc once it's working in old style c++.

Many Thanks for help, much appreciated

[redhead]

Pseudocode

if(!(array_size%4)) /* ensure we can shift 4 items on each run */
  store array[array_size -3] in temp_1
  store array[array_size -2] in temp_2
  store array[array_size -1] in temp_3
  store array[array_size] in temp_4
  while(array[index])
    switch array[index] with temp_1
    switch array[index+1] with temp_2
    switch array[index+2] with temp_3
    switch array[index+3] with temp_4
    index+=4

And you couldn't think of that yourself ?

By the way, what is old C++ ?? you've got the STL right there, why not use it??

[Salchester]

Could you include the structure & include files etc in the coding as I am not very familiar with arrays and I can’t work things out using snippets of code.

Many Thanks

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
What I mean by “Old C++” is the use of the old header files i.e. #include<iostream.h>

[redhead]

So you're talking about standard C, not C++

Yea I'll give you an example to show how it is done.. But you gotta understand what is happening, if it turns out this is an assignment I've just done for you, then I'm gonna need a hell of alot more from your part the next time.

#include <stdio.h>   /* printf() */
#include <string.h>  /* strlen(), strcpy() */
#include <stdlib.h>  /* malloc(), realloc(), free() */

int main()
{
  int i=0,j=0,size=0;

  /* the list to sort, could've been 
   * created any way you like.. 
   */
  char *str_arr[] = {"Jonny", "Janie", "Billy", "Georg", 
		       "David", "Kelly", "Brian", "Steve", 
		       "Allan", "Sammy", "Doris", "Bobby", NULL};

  /* this is the actual array that's beeing sortet */
  char** str_array;
  char *tmp1, *tmp2;
  /* make room for our array to be sortet */
  size=sizeof(str_arr)/sizeof(*str_arr);
  str_array = (char**)malloc (size*sizeof (char*));

  /* copy everything into our array */
  for(i=0;str_arr[i];++i)
    {
      str_array[i] = (char*) malloc(strlen(str_arr[i])*sizeof(char));
      strcpy(str_array[i], str_arr[i]);
    }
  /* NULL terminate the array */
  str_array[i] = NULL;

  /* Verify theres atleast four (4) items in the end to shift */
  size=i-4;
  if(size > 0)
    {
      printf("Array befor shifting operations:");
      for(i=0;str_array[i];++i)
	printf("%c%d) %s", (i%4?'\t':'\n'), (i+1), str_array[i]);
      printf("\n");      
      /* shift last four items to the front */
      for(i=0;str_array[i];++i,++j)
	{
	  /* 
	   * For efficiency we use the last four places in the
	   * array over and over again to simulate a O(N) runtime 
	   *
	   * The theory is this:
	   * 
	   * Last four items should be placed as first four items
	   * 1) swap fourth last item with first item from pointer
	   * 2) swap third last item with second item from pointer
	   * 3) swap second last item with third item from pointer
	   * 4) swap last item with fourth item from pointer
	   * 6) repeat 1 - 4 untill either 
	   *      a) Pointer is placed where swap is placed (hence b)
	   *      b) Theres no more items to swap
	   */
	  if(!(i%4))
	    j=size; /* keep swap pointer to last 4 locations */
	  if(i>=j)
	    break; /* break if current pointer is at swap pointer */
	  /* make room for our swap */
	  tmp1 = (char*) malloc(sizeof(char)*strlen(str_array[i]));
	  tmp2 = (char*) malloc(sizeof(char)*strlen(str_array[j]));
	  /* swap what's at current location and swap pointer */
	  strcpy(tmp1, str_array[i]);
	  strcpy(tmp2, str_array[j]);
	  /* since our str_array is allocated, and we have no idear
	   * if the swap item is larger than what's previusly here
	   * then reallocate the memory 
	   */
	  str_array[i] = (char*) realloc(str_array[i], 
					 sizeof(char)*strlen(tmp1));
	  str_array[j] = (char*) realloc(str_array[j],
					 sizeof(char)*strlen(tmp2));
	  /* swap the items back into our array */
	  strcpy(str_array[i], tmp2);
	  strcpy(str_array[j], tmp1);
	  /* We better make 'nice' with the system and 
	   * give back what we've currently borrowed
	   */
	  free(tmp1);
	  free(tmp2);
	}
      printf("\nArray after shifting operations:");
      for(i=0;str_array[i];++i)
	printf("%c%d) %s", (i%4?'\t':'\n'), (i+1), str_array[i]); 
      printf("\n");
    }
  else
    printf("Error: There should be atleast 4 items in the list\n");
  /* free everything up, that we've used so far */
  for(i=0;str_array[i];++i)
    free(str_array[i]);
  free(str_array);
  return 0;
}

[Salchester]

I do mean c++, what will the code you have be like in c++?

This is what i have so far…

#include <iostream.h>

struct game
{
  char name[20];
}
game unsortednames[36];

int main (void)
{

  return 0;
}

[redhead]

Using .h in the include names aren't C++
If you look carefuly on my code example, and read the comments, you'll soon notice the shifting mechanism will be the same in your case, nomatter if you call it C or C++

[Valmont]

Heyyy I forgot about this thread. I'll be back home in a few hours.

[Valmont]

You should approach this problem as a "rotation problem". This leads to this memory and time efficient algorithm. Also notice the usage of std::swap. Swapping takes a constant time now, which is fast obviously.

#include <iostream>
#include <string>

static std::string x[] = 
{ "Jonathan", "Jane", "David", "Kellie", "Lucy", "Jamie", "Mark" };

//------------------------------------------------

void rotate_up_reverser(unsigned i, unsigned j)
{  
  std::string t;
  while (i < j) {
    x[i].swap(x[j]);
    i++;
    j--;
  }
}

//------------------------------------------------

void rotate_up(int rotdist, int n)
{  rotate_up_reverser(0, rotdist-1);
  rotate_up_reverser(rotdist, n-1);
  rotate_up_reverser(0, n-1);
}

//------------------------------------------------

int main()
{
  unsigned Size = sizeof x / sizeof *x;
  
  //Rotate the array. With n = Size, we wish to rotate the whole array.
  //With "Size - last_four_elements" ...
  //...we wish to rotate the "whole array" up 3 spots.
  rotate_up(3, Size);
  
  //Let's see what we got after rotation.
  for(unsigned i = 0; i < Size; ++i)
  {
    std::cout<<x[i]<<std::endl;
  }
  return 0;
}

[Salchester]

Can you write it without using namespaces please as i don't understand them as yet, i am going to write in without them first, then once i have mastered how to use them etc i will convert my code.

Many Thanks

[Valmont]

Add:
"using namespace std;" below the includes then remove all "std::" occurances.