7
\$\begingroup\$

This is primarily a container for quicksort and mergesort:

#include "c_arclib.cpp"
template <class T> class dynamic_array
  {
  private:
    T* array;
    T* scratch;
  public:
    int size;
    dynamic_array(int sizein)
      {
      size=sizein;
      array = new T[size]();
      }
    void print_array()
      {
      for (int i = 0; i < size; i++) cout << array[i] << endl;
      }
    void merge_recurse(int left, int right)
      {
      if(right == left + 1)
        {
        return;
        }
      else
        {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length/2;
        int l = left, r = left + midpoint_distance;
        merge_recurse(left, left + midpoint_distance);
        merge_recurse(left + midpoint_distance, right);
        for(i = 0; i < length; i++)
          {
          if((l < (left + midpoint_distance)) && (r == right || array[l] > array[r]))
            {
            scratch[i] = array[l];
            l++;
            }
          else
            {
            scratch[i] = array[r];
            r++;
            }
          }
        for(i = left; i < right; i++)
          {
          array[i] = scratch[i - left];
          }
        }
      }
    int merge_sort()
      {
      scratch = new T[size]();
      if(scratch != NULL)
        {
        merge_recurse(0, size);
        return 1;
        }
      else
        {
        return 0;
        }
      }
    void quick_recurse(int left, int right) 
      {  
      int l = left, r = right, tmp;
      int pivot = array[(left + right) / 2];
      while (l <= r)
        {
        while (array[l] < pivot)l++;
        while (array[r] > pivot)r--;
        if (l <= r) 
          {
          tmp = array[l];
          array[l] = array[r];
          array[r] = tmp;
          l++;
          r--;
          }
        }
      if (left < r)quick_recurse(left, r);
      if (l < right)quick_recurse(l, right);
      }  
    void quick_sort()
      {
      quick_recurse(0,size);
      }
    void rand_to_array()
      {
      srand(time(NULL));
      int* k;
      for (k = array; k != array + size; ++k)                                             
        { 
        *k=rand();                                      
        } 
      }
  };
int main()
  {
  dynamic_array<int> d1(10);
  cout << d1.size;
  d1.print_array();
  d1.rand_to_array();
  d1.print_array();
  d1.merge_sort();
  d1.print_array();
  }
\$\endgroup\$
3
\$\begingroup\$

My first comment is its named badly.

dynamic_array implies that I can use [] operator on it and get a value out.

You have owned RAW pointers in your structure.

private:
  T* array;
  T* scratch;

First this means you need to look up RAII to make sure these members are correctly deleted.

Second you you need to look up the rule of three (or 5 in C++11) to make sure they are copied correctly.

You have owned RAW pointers in your structure. This means you need to correctly manage the object as a resource. This means constructions/destruction/copy (creation and assignment) need to be taken care of correctly.

Either do this manually or use a standard container that will do it for you. I suggest a standard container.

void print_array()
  {
  for (int i = 0; i < size; i++) cout << array[i] << endl;
  }

If you are going to write print_array at least write it so that it can use alternative stream (not just std::cout). Then write the output operator.

std::ostream& operator<<(std::ostream& stream, dynamic_array const& data)
{
     data.print_array(stream); // After you fix print_array
     return stream;
}

Also note that a method that access data but does not modify the state of the object should be marked const. So the signature should be: void print_array() const

Are the following members really part of the array?

void merge_recurse(int left, int right)
int merge_sort()
void quick_recurse(int left, int right)

OK. Lets assume they are for now.
Then void merge_recurse(int left, int right) should be a private member. There should be no reason to call this from externally.

  scratch = new T[size]();
  if(scratch != NULL)

scratch will Never be NULL.

I think merge (in merge_recurse) is easier to write than you are making it:

    int index = 0;
    int l = left;
    int r = midpoint;
    while((l < midpoint) && (r < right))
    {
      scratch[index++] = (array[l] > array[r]))
                           ? array[l++]
                           : array[r++];
    }
    // One of the two ranges is empty.
    // copy the other into the destination.
    while(l < midpoint)
    {
        scratch[index++] = array[l++];
    }
    while(r < right)
    {
        scratch[index++] = array[r++];
    }

You should only call srand() once in an application:

void rand_to_array()
  {
  srand(time(NULL));

By putting srand() inside the structure you are opening it up to be called multiple times. Call it once just after main() then don't call it again.

When you can use the standard tools:

      tmp = array[l];
      array[l] = array[r];
      array[r] = tmp;

Can be replaced with:

 std::swap(array[l], array[r]);

I am relatively sure these two are wrong:

  while (l <= r)
    if (l <= r) 

They should be:

  while (l < r)
    if (l < r) 
\$\endgroup\$
  • \$\begingroup\$ +1 but I must disagree with the bit about using a standard container. The OP is reimplementing a poor man's version of vector. Of course, he should normally use a vector, but if reimplementing vector for learning purposes it would be silly to use vector or another standard container to do it. \$\endgroup\$ – Winston Ewert Nov 2 '11 at 1:14
  • \$\begingroup\$ @WinstonEwert: I was not sure if his goal was a poor man vector or just a structure so that he could practice sorting with. My advice design the class for one particular use. Thus in the case use a standard container to hold the data and implement the sorting here. If this is a poor man's vector then fine but in that case my advice would be to factor out the sorting stuff into its own class. \$\endgroup\$ – Martin York Nov 2 '11 at 16:11
  • \$\begingroup\$ Posted New Code. Thank you, I re-wrote merge_sort alltogether and implemented some of your changes. This is a class so I can practice sorting and interview...but I'm also curious that b.c. I "own" it..maybe I can beat Vector in performance for special cases....there is still alot of work to to do on this... \$\endgroup\$ – user7459 Nov 6 '11 at 16:47
  • \$\begingroup\$ You raised so many questions I do not think I have time to answer them...particularly the issue with raw pointers...how can I verify their destruction? \$\endgroup\$ – user7459 Nov 6 '11 at 16:52
  • \$\begingroup\$ @Chris Aaker: You will not beat vector in any situation. If you find that you have written code that is faster than vector then you have forgotten to do something. \$\endgroup\$ – Martin York Nov 6 '11 at 17:33
2
\$\begingroup\$

This is just a review regarding coding style. Because... your code is impossible to read. And because of the poor coding style alone, you will get less replies whenever you post it to sites like this one.

At a very minimum, you should keep empty rows between every function declaration, or the program look like one big goo. Including empty rows here and there inside the function bodies as well, to indicate which sections of code that belong together.

You should also consider changing indention style to something more conventional. The most common form by far is not to indent the braces, but indent the contents between them. Another less common but acceptable style is to indent the braces and then indent the contents between them.

Here is an example of what your code would look like, using one of the most common styles:

#include "c_arclib.cpp"

// space here

template <class T>   // template specification is most often put on a row of its own
class dynamic_array
{
  private:
    T* array;
    T* scratch;

 // space here, private and public dont belong together

  public:
    int size;

    dynamic_array (int sizein)
    {
      size=sizein;
      array = new T[size]();
    }

    // space between all functions!!!

    void print_array ()
    {
      for (int i = 0; i < size; i++) // always use braces to avoid bugs!
      { 
        cout << array[i] << endl;
      }
    }

    void merge_recurse (int left, int right)
    {
      if(right == left + 1)
      {
        return;
      }
      else
      {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length/2;
        int l = left, r = left + midpoint_distance;

        // space here, end of variable declarations

        merge_recurse(left, left + midpoint_distance);
        merge_recurse(left + midpoint_distance, right);

        for(i = 0; i < length; i++)
        {
          /* The if statement would really benefit from getting split up in several
             statements. Replace the bool variable names below with something meaningful. 
             (I haven't bothered to look at what your code actually does). */

          bool less_midpoint  = l < (left + midpoint_distance);
          bool equal          = r == right;
          bool larger         = array[l] > array[r];

          if(less_midpoint && (equal || larger))
          {
            scratch[i] = array[l];
            l++;
          }
          else
          {
            scratch[i] = array[r];
            r++;
          }
        }

        for(i = left; i < right; i++)
        {
          array[i] = scratch[i - left];
        }
      } // else   /* <- Write "else" or similar in a comment to indicate to what
                     code a brace belongs to inside a complex, long nested code */
    }  // merge_recurse

    int merge_sort ()
    {
      scratch = new T[size]();
      if(scratch != NULL)
      {
        merge_recurse(0, size);
        return 1;
      }
      else
      {
        return 0;
      }
    }

    void quick_recurse (int left, int right) 
    {  
      int l = left, r = right, tmp;
      int pivot = array[(left + right) / 2];

      while (l <= r)
      {
        while (array[l] < pivot) // always use braces to avoid bugs!
        {
          l++;
        }
        while (array[r] > pivot) // always use braces to avoid bugs!
        {
          r--;
        }

        if (l <= r) 
        {
          tmp = array[l];
          array[l] = array[r];
          array[r] = tmp;
          l++;
          r--;
        }
      } // while (l <= r)

      if (left < r)
      {
        quick_recurse(left, r);
      }
      if (l < right)
      {
        quick_recurse(l, right);
      }
    }  

    void quick_sort ()
    {
      quick_recurse(0,size);
    }

    void rand_to_array ()
    {
      srand(time(NULL));
      int* k;

      for (k = array; k != array + size; ++k)                                             
      { 
        *k=rand();                                      
      } 
    }
};

int main()
{
  dynamic_array<int> d1(10);
  cout << d1.size;
  d1.print_array();
  d1.rand_to_array();
  d1.print_array();
  d1.merge_sort();
  d1.print_array();
}
\$\endgroup\$
  • \$\begingroup\$ I agree your code looks nicer...I get tired of scrolling so I bunch it togther too much....screen is too small \$\endgroup\$ – user7459 Nov 6 '11 at 16:37
  • \$\begingroup\$ @Chris Aaker: You should get yourself a modern or semi-modern IDE, so that you can jump directly to a specific function in the source code without any scrolling. \$\endgroup\$ – Lundin Nov 7 '11 at 7:38
  • \$\begingroup\$ I'm finally updating my style to the Zend PHP Style... \$\endgroup\$ – user7459 Nov 22 '11 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy