Dynamic Array - Improvements - 0 - not complete

Question

EDIT (changes) (code posted)

Ended up re-writing merge_sort
Removed merge_sort and quick_sort and created separate classes
Implemented >> operator for printing

TO DO

Needs a resize function to make it dynamic...Currently it is primarily a container for quick_sort and merge_sort.

CODE

#include "c_include.cpp"
using namespace std;
template <typename> class quick_inner;
template <typename> class merge_inner;
template <class T> class dynamic_array
  {
  protected:
    T* array;
  public:
    int size;
    void rorder();
    void order();
    void randorder();
    void randorder_new();
    void print_operator(ostream&)const;
    dynamic_array(int sizein)
      {
      size=sizein;
      array=new T[size]();
      }
    void merge_sort()
      {
      merge_inner<T> M1(array,size);
      }
    void quick_sort()
      {
      quick_inner<T> Q1(array,size);
      }
  };
template <class T> void dynamic_array<T>::print_operator(ostream &os=cout)const
  {
  for (int i = 0; i < size; i++) os << array[i] << endl;
  }
template <class T> void dynamic_array<T>::randorder()
  {
  srand(time(NULL));
  int *ap,i=0,x;
  for(ap=array;ap!=array+size;++ap)                                             
    { 
    *ap=i;
    ++i;        
    } 
  for(i=0;i<size;++i)
    {
    x=(rand()%size);
    int tmp=array[x];
    array[x]=array[i];
    array[i]=tmp;   
    }
  }
template <class T> void dynamic_array<T>::randorder_new()
  {
  srand(time(NULL));
  int *ap,i=0,x;
  for(ap=array;ap!=array+size;++ap)                                             
    { 
    *ap=i;
    ++i;        
    } 
  for(i=0;i<size;++i)
    {
    x=(rand()%size);
    int tmp=array[x];
    array[x]=array[i];
    array[i]=tmp;   
    }
  }
template <class T> void dynamic_array<T>::order()
  {
  int *ap,i=0;
  for(ap=array;ap!=array+size;++ap)                                             
    { 
    *ap=i;
    ++i;        
    } 
  }
template <class T> void dynamic_array<T>::rorder()
  {
  int *ap,i=size-1;
  for(ap=array;ap!=array+size;++ap)                                             
    { 
    *ap=i;
    --i;        
    } 
  }
template<class T> ostream& operator<<(ostream& stream, dynamic_array<T> const& data) 
  { 
  data.print_operator(stream);
  return stream; 
  }   
template <class T> class merge_inner 
  {
  public:
    merge_inner(T *array_in,int size_in)
      {
      array=array_in;
      size=size_in;
      scratch = new T[size]();
      if(scratch != NULL){merge_recurse(0, size);}
      }
  private:
    int size;
    T *array;
    T *scratch;
    void flip_if_unordered(int &x, int &y)
      {
      if(array[x]>array[y])
        {
        int tmp=array[x];
        array[x]=array[y];
        array[y]=tmp;
        }
      }
    void merge_algo(int &left, int &right_begin, int &right)
      {
      int iter,iter_left=left,iter_right=right_begin;  
      for(iter=left;iter<=right;++iter)
        {
        if( (iter_right>right) || ((iter_left < right_begin) && (array[iter_left]<=array[iter_right])))
          {
          scratch[iter]=array[iter_left];
          ++iter_left;
          }
        else
          {
          scratch[iter]=array[iter_right];
          ++iter_right;
          }
        }
      for(iter=left;iter<=right;++iter){array[iter]=scratch[iter];}
      }
    void merge_recurse(int left,int right)
      {
      int left_end=(left+((right-left)/2)); 
      int right_begin=left_end+1;  
      if(((left+1)==right)){flip_if_unordered(left,right);return;}
      else if ((left==right)){return;}
      else
        { 
        merge_recurse(left,left_end);               
        merge_recurse(right_begin,right);  
        merge_algo(left,right_begin,right);
        }   
      }
  };
template <class T> class quick_inner
  {
  private:
    int size;
    T* array;
  public:
    quick_inner(T *array_in,int size_in)
      {
      array=array_in;
      size=size_in;
      quick_recurse(0,size);
      }
    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);
      }
  };

Loki Astari · Accepted Answer · 2011-11-02 00:37:10Z

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)

+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. — Winston Ewert, Nov 2 '11 at 1:14
@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. — Loki Astari, Nov 2 '11 at 16:11
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... — user7459, Nov 6 '11 at 16:47
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? — user7459, Nov 6 '11 at 16:52
@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. — Loki Astari, Nov 6 '11 at 17:33

Lundin · Answer 2 · 2011-11-04 12:48:03Z

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();
}

I agree your code looks nicer...I get tired of scrolling so I bunch it togther too much....screen is too small — user7459, Nov 6 '11 at 16:37
@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. — Lundin, Nov 7 '11 at 7:38

asked	2 years ago
viewed	249 times
active	2 years ago

Dynamic Array - Improvements - 0 - not complete

2 Answers

Your Answer

Dynamic Array - Improvements - 0 - not complete

2 Answers

Did you find this question interesting? Try our newsletter

Your Answer

Sign up or login

Post as a guest

Related