Thread: Sorting Help
View Single Post
Old 10-17-2005, 07:56 AM   #12 (permalink)
Valmont
[code][/code] enforcer
 
Valmont's Avatar
 
Join Date: Mar 2003
Location: Netherlands
Posts: 1,544
Valmont is on a distinguished road
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.

Code:
#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;
}
__________________
Valmont is offline   Reply With Quote