Member Avatar for bones10925

Hi guys I am new here and I need some assitance with my Merge Sort. I have it written but its not working correctly. It just gives me -1, 1.

The way my program works is that the sorts are handled inside the Class Sort so there is no need for passing the array around. Just ignore the excess comments and time functions.


Thanks for any help, and hopefully when I get some free time I can help around here.


bones10925

//////////////////////////////////////////////////////////////////////
/// @file main.cpp
/// @author Kyle Ensign  CS 253  Section 1A
/// @brief This file is the main driver for this program. It asks
///  the user for input, runs it through a sort, and then tells the
///  user how many milliseconds the sort took to run
//////////////////////////////////////////////////////////////////////



#include "sort.h"
#include <time.h>
#include <sys/time.h>

#include <iostream>
using namespace std;


int main()
{
  timeval val1;
  timeval val2;

  int array[10];
  int counter = 10;
  for(int i = 0;i < 10; i++)
  {
    array[i] = counter;
    counter--;
  }

  Sort s(array, 10);
  s.output();
  gettimeofday(&val1, NULL);
  //s.insertionSort();


  s.mergeSort(1, 9);
  gettimeofday(&val2, NULL);
  s.output();

  suseconds_t sum1 = (val1.tv_sec * 1000000) + val1.tv_usec;
  suseconds_t sum2 = (val2.tv_sec * 1000000) + val2.tv_usec;

  cout << "Time: " << sum2-sum1 << " microseconds" << endl;




  return 0;
}
//////////////////////////////////////////////////////////////////////
/// @file sort.cpp
/// @author Kyle Ensign  CS 253  Section 1A
/// @brief This file contains the Sort Class defined functions
//////////////////////////////////////////////////////////////////////

#include "sort.h"
using namespace std;


//////////////////////////////////////////////////////////////////////
/// @fn Sort(int *a, int n)
/// @brief This function constructs a sort object
/// @pre The size n has to be equal to the size of the array
/// @post This function constructs a sort object with its pointer
///  array and length
/// @param a pointer array of the sort class
/// @param n size of the pointer array
//////////////////////////////////////////////////////////////////////



Sort::Sort(int *a, const int n)
{
  array = a;
  numElements = n;
  cout << "numElements " << n << endl;
}

//////////////////////////////////////////////////////////////////////
/// @fn void merge(const int p, const int q, const int r)
/// @brief This function merges the two parts of the array back together
/// @pre Two positive arrays array[p...q] & array[q+1...r] are sorted
/// @post array[p...r] is a sorted array and a permutation to the
///  original array[p...q] & array[q+1...r]
/// @param p start of the left array
/// @param q start of the right array
/// @param r end of the right array
//////////////////////////////////////////////////////////////////////
void Sort::merge(const int p, const int q, const int r)
{
  //****Checks the pre condition of this function*******
  /*bool flag = true, flag2 = true;
  int index = p;
  while(flag == true && index < q)
  {
    if(array[index] >= array[index+1])
    {
      flag = false;
    }
  }
  assert(flag);
  index = q+1;
  while(flag2 == true && index < r)
  {
    if(array[index] >= array[index+1])
    {
      flag2 = false;
    }
  }
  assert(flag2);
  //***********************************************/

  int n1 = q - p + 1;
  int n2 = r - q;

  int *left=new int[n1+2];
  int *right=new int[n2+2];


 // int left[n1+2];
 // int right[n2+2];

  //int i = 0, j = 0, k = 0;

  //comment here
  //cout << "left: ";
  for(int i = 1; i <= n1; i++)
  {
    left[i] = array[p + i - 1];
  //  cout << left[i] << " ";
    //assert(left[i]==array[p+i-1]);
  }
  for(int j = 1; j <= n2; j++)
  {
    right[j] = array[q+j];
  }


  left[n1+1] = UINT_MAX;
  right[n2+1] = UINT_MAX;
  int i=1;
  int j=1;

  for(int k = p; k <= r; k++)
  {
    if(left[i] < right[j])
    {
      array[k] = left[i];
      i++;
    }
    else
    {
      array[k] = right[j];
      j++;
    }
  }

  delete [] left;
  delete [] right;


  //***tests the post condition of this function****
  /*bool flag3 = true;
  index = p;
  while(flag == true && index < r)
  {
    if(array[index] >= array[index+1])
    {
      flag = false;
    }
  }
  assert(flag);
  //***********************************************/
  return;
}

//////////////////////////////////////////////////////////////////////
/// @fn void mergeSort(const int p, const int r)
/// @brief Using recursion, this function sorts the array
/// @pre none
/// @post array[p...r] is sorted and is a permutation of the original
///  of array[p...r]
/// @param p start of the array
/// @param r end of the array
//////////////////////////////////////////////////////////////////////
void Sort::mergeSort(const int p, const int r)
{
  int mid = 0;
  if(p < r)
  {
    mid = (p+r) / 2;
    mergeSort(p, mid);
    mergeSort(mid+1, r);
    merge(p, mid, r);
  }

  //***Tests the post condition of this function***
  /*bool flag = true;
  int i = p;
  while(flag && i < r)
  {
    if(array[i] >= array[i+1])
      {
        flag = false;
    }
  }
  assert(!flag);
  //**********************************************/

  return;
}


//////////////////////////////////////////////////////////////////////
/// @fn void insertionSort()
/// @brief This function sorts the array using the Insertion Sort
/// @pre none
/// @post array[p...r] is sorted and is a permutation of the original
///  array[p...r]
//////////////////////////////////////////////////////////////////////
void Sort::insertionSort()
{
  int key = 0;
  int i, j;

  for(j=1;j<numElements;j++)
  {
    key = array[j];
    i=j;
    while(i>0&&array[i-1]>key)
    {
      array[i]=array[i-1];
      i--;
    }
    array[i]=key;
  }

//***Tests the post condition of this function***
bool flag = true;
int k = 0;
while(flag && k < numElements)
{
  if(array[k] >= array[k])
  {
    flag = false;
  }
}
assert(!flag);
//**********************************************
  return;
}

//////////////////////////////////////////////////////////////////////
/// @fn void output()
/// @brief This function outputs the sorted array
/// @pre none
/// @post array[p...r] is sorted and is a permutation of the original
///  of array[p...r]
/// @param p start of the array
/// @param r end of the array
//////////////////////////////////////////////////////////////////////
void Sort::output()
{
 cout<<"The sorted list is : ";
 for(int i = 0;i < numElements;i++)
 {
   cout << array[i] << " ";
 }
 cout<<endl;
 return;
}
//////////////////////////////////////////////////////////////////////
/// @file sort.h
/// @author Kyle Ensign  CS 253  Section 1A
/// @brief This file contains the Sort Class with its functions
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
/// @class Sort
/// @brief This class contains both Merge Sort & Insertion Sort
//////////////////////////////////////////////////////////////////////

#ifndef SORT_H
#define SORT_H

#include <iostream>
using namespace std;


class Sort
{
  public:
    Sort(int *a, const int n);
    void merge(const int p, const int q, const int r);
    void mergeSort(const int p, const int r);
    void insertionSort();
    void output();

   private:
    int numElements;
    int *array;

};


#endif
  • 2 Contributors
  • 1 Reply
  • 103 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by kylcrow
Member Avatar for kylcrow

I don't think your merge sort is completely done yet. Someone tell me if I am wrong (which is very possible), but doesn't MergeSort work more like this... (keep in mind that this way, you are in fact passing arrays around)

void Merge_Sort(int array_MSort[], int* temp, int left, int right)
{
  if (left == right)
    {
      return;
    }
  
  int mid = (left+right)/2;

  Merge_Sort(array_MSort, temp, left, mid);
  Merge_Sort(array_MSort, temp, mid+1, right);
  
  for (int i = left; i <= right; i++)
    {
      temp[i] = array_MSort[i];
    }
  
  int l = left;
  int r = mid + 1;
  
  for(int j=left; j<=right; j++)
    {
      if (l == mid+1)
	{
	  array_MSort[j] = temp[r++];
	}
      
      else if (r > right)
	{
	  array_MSort[j] = temp[l++];
	}
      
      else if(temp[l] < temp[r])
	{
	  array_MSort[j] = temp[l++];
	}
      
      else
	{
	  array_MSort[j] = temp[r++];
	}
    }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.