sorting array/copying

**kakashi316** · 05-03-2009

Im trying to write a program where i put an array into 4 different functions and time the sorts.To do that im supposed to write a copy function that copys the original array into a copied array that i sent into the function.

this is my current code:

Code:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<fstream>
#include<string.h>
using std::rand;
using std::srand;
using namespace std;
//FUNCTIONS START
int BubbleSort(int numbers[],int arraysize);
int insertion_sort(int numbers[], int arraysize);
int quickSort(int numbers[], int array_size);
int q_sort(int a[], int left, int right);
int heapSort(int numbers[], int array_size);
int heapify(int numbers[],int array_size);
int siftDown(int numbers[], int start,int end);
int copy(int copiedarray[],int numbers[]);
//FUNCTIONS END
ofstream outf("f:Proj1-Output.dat", ios::out);
ifstream inf("f:Proj1-Input.dat", ios::in);


//-------------------MAIN-----------------------------------------------------------
int main()
{
     float t1, t2, t3, t4;
    long int start,end;
     int array_cnt=0;         
     int results1;
     int results2;
     int results3;
     int results4;
     srand(time(0));
     int arraysize = 10;
     int numbers[arraysize];
     int copiedarray[arraysize];


     
outf<<"SIZE   "<<"QUICK "<<"HEAP "<<"BUBBLE "<<"INSERTION "<<endl;      
for (int global=1; global<=20; global++)     
{

                for (int i = 0; i < arraysize; i++)
                {  
               
                array_cnt++;     
                }

outf<<array_cnt<<"    ";
                                 copy(copiedarray,numbers);
                                 start= clock();
                                 results1=quickSort(copiedarray,arraysize);
                                 end= clock();
                                 outf<<results1;                                                                         
                                 outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
                                 
                                 start= clock();
                                 results2= insertion_sort(numbers,arraysize);      
                                 end= clock();                                
                                 
                                 start= clock();
                                 results3= BubbleSort(numbers,arraysize);
                                 end= clock();                                     
                                 
                                 start= clock();
                                 results4= heapSort(numbers,arraysize);
                                 end= clock();
}
        
        system("pause");
         return 0;

}    
//END OF MAIN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!







//BUBBBLE START
int BubbleSort(int a[], int array_size)
{

    
     int i, j, temp;
     for (i = 0; i < (array_size - 1); ++i)
     {
          for (j = 0; j < array_size - 1 - i; ++j )
          {
               if (a[j] > a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }
}
//BUBBLE END


//INSERTION START
int insertion_sort(int a[], int array_size)
{
     int i, j, key;
     for(j = 1; j < array_size; j++)    
    {
           key = a[j];
           for(i = j - 1; (i >= 0) && (a[i] > key); i++)   
          {
                 a[i+1] = a[i];
          }
         a[i+1] = key;    
     }
}
//INSERTION END


//QUICK START
int quickSort(int a[], int array_size)
{

  int i;
  q_sort(a, 0, array_size - 1);
}

int q_sort(int a[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = a[left];
  while (left < right)
  {
    while ((a[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      a[left] = a[right];
      left++;
    }
    while ((a[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      a[right] = a[left];
      right--;
    }
  }
  a[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(a, left, pivot-1);
  if (right > pivot)
    q_sort(a, pivot+1, right);
}
//QUICK END


//HEAP START


int heapify(int a[],int array_size)
{

    int start= (array_size- 2) / 2;
    for(; start >= 0; start--)     
    {
     siftDown(a, start, array_size-1);
     }
     return 0;
}
int siftDown(int a[], int start,int end)
{
    int root;
    int child;
    root=start;
    while (root * 2 <= end)
    {
          if (root*2 == end)
			child = root * 2;
		else if(a[root * 2] > a[root * 2 + 1])
			child = root * 2;		
		else
			child = root * 2 + 1;


		if(a[root] < a[child])
		{
			swap(a[root], a[child]);
			root = child;
		}
		else
			return 0;
   }
}
int heapSort(int a[], int array_size)
{
    int i;    
      int end;    
	heapify(a, array_size);
	

	for (end = array_size - 1; end >= 1; end--)
	{
		swap(a[end], a[0]);
		siftDown(a, 0, end - 1);		
	}
}
//HEAP END

int copy(int a[],int b[])
{
     int arraysize; 
     for (int i = 0; i < arraysize; i++)
                {   
                int a[i];
                int b[i];
                a[i]=b[i];   
                }
     return 0;
}

i know the copy function is not completely right and my current problem is that nothing displays.any help is massively appreciated.Note:i am not the best programmer in the world,so be kind.

**anon** · 05-03-2009

Code:

int copy(int a[],int b[])

With this signature it couldn't possibly work, since there is no way of knowing how large the arrays are.

Code:

int arraysize;

This is just an uninitialized variable. Without a change to the function arguments it won't even be possible to find out what its value should be.

Code:

                int a[i];
                int b[i];

Why would you declare these arrays in the loop, shadowing the arrays that you really want to copy?

Code:

     const int arraysize = 10;
     int numbers[arraysize];
     int copiedarray[arraysize];

Now this would be legal C++.

**kakashi316** · 05-03-2009

is this any better?

Code:

int copy(int copiedarray[],int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                int numbers[arraysize];
                int copiedarray[arraysize];
                copiedarray[arraysize]=numbers[arraysize];   
                }
     return 0;
}

**iMalc** · 05-03-2009

Originally Posted by kakashi316

is this any better?

Code:

int copy(int copiedarray[],int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                int numbers[arraysize];
                int copiedarray[arraysize];
                copiedarray[arraysize]=numbers[arraysize];   
                }
     return 0;
}

You're still trying to declare second copies of the arrays passed in. You don't need a return value either as it should be a void function.
You only need two lines of code in the function body for this. Delete all but the two most important lines of code from the above function body, change the function to return void, and you're done.

Your heapsort has an unused variable 'i' in it too.

I see you got the quicksort from here:
C/C++ flow chart: void quickSort(int numbers[], int array_size)
It looks a little different to normal, but should also work.

**kakashi316** · 05-03-2009

so it should be

Code:

void copy(int copiedarray[],int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                copiedarray[arraysize]=numbers[arraysize];   
                }
     return 0;
}

**kakashi316** · 05-03-2009

im working with in a group and this is what my friend got modified by me

Code:

include<iostream>
#include<iomanip>
#include<cstdlib>
#include<fstream>
using std::rand;
using std::srand;
using namespace std;
//FUNCTIONS START***************************************************************
int BubbleSort(int numbers[],int arraysize);
int insertion_sort(int numbers[], int arraysize);
int quickSort(int numbers[], int array_size);
int q_sort(int a[], int left, int right);
int heapSort(int numbers[], int array_size);
int heapify(int numbers[],int array_size);
int siftDown(int numbers[], int start,int end);
void copy(int array1[], int size);
//FUNCTIONS END*****************************************************************
ofstream outf("f:Proj3-Output.dat", ios::out);
ifstream inf("f:Proj3-input.dat", ios::in);
//******************************************************************************
//**********************************MAIN****************************************
//******************************************************************************
int main()
{
     float t1, t2, t3, t4;
     int array_cnt=0;          
     int results1;
     int results2;
     int results3;
     int results4;
     int x_1, x_2;
     srand(time(0));
     int arraysize = 10000;
     int numbers[arraysize];
     for (int i = 0; i < arraysize; i++)   
     numbers[i] = 1+ rand() % 100000;

     
outf<<"SIZE   "<<"QUICK "<<"HEAP "<<"BUBBLE "<<"INSERTION "<<endl;      
for (int global=1; global<=20; global++)
{    
for (int i = 0; i < arraysize; i++)
                {   
               arraysize=arraysize+1500;
                array_cnt++;     
                } 
copy(numbers,arraysize);
results1=BubbleSort(numbers,arraysize);

copy(numbers,arraysize);
results2=insertion_sort(numbers, arraysize);

copy(numbers,arraysize);
results3=quickSort(numbers, arraysize);

copy(numbers,arraysize);
results4=heapSort(numbers, arraysize);                                                          

}         
         return 0;

}    

//******************************************************************************
//********************************** END OF MAIN********************************
//******************************************************************************

//******************************************************************************
//********************************BUBBBLE START*********************************
//******************************************************************************

int BubbleSort(int a[], int array_size)
{    
  long int start, end;
  start= clock();  
     int i, j, temp;
     for (i = 0; i < (array_size - 1); ++i)
     {
          for (j = 0; j < array_size - 1 - i; ++j )
          {
               if (a[j] > a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }
end= clock();
outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
     for(i=0; i<array_size; i++)
     cout<<setw(7)<<a[i];
}

//******************************************************************************
//********************************BUBBBLE END***********************************
//******************************************************************************

//******************************************************************************
//******************************INSERTION START*********************************
//******************************************************************************
int insertion_sort(int a[], int array_size)
{
  long int start, end;
  start= clock();
     int i, j, key;
     for(j = 1; j < array_size; j++)    //Notice starting with 1 (not 0)
    {
           key = a[j];
           for(i = j - 1; (i >= 0) && (a[i] > key); i++)   //Move smaller values up one position
          {
                 a[i+1] = a[i];
          }
         a[i+1] = key;    //Insert key into proper position
     }
end= clock();
outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
     for(i=0; i<array_size; i++)
     cout<<setw(7)<<a[i];
}
//******************************************************************************
//********************************INSERTION END*********************************
//******************************************************************************

//******************************************************************************
//**********************************QUICK START*********************************
//******************************************************************************
int quickSort(int a[], int array_size)
{
  long int start, end;
  start= clock();
  int i;
  q_sort(a, 0, array_size - 1);
  end= clock();
  outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
  for(i=0; i<array_size; i++)
  cout<<setw(7)<<a[i];
}

int q_sort(int a[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = a[left];
  while (left < right)
  {
    while ((a[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      a[left] = a[right];
      left++;
    }
    while ((a[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      a[right] = a[left];
      right--;
    }
  }
  a[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(a, left, pivot-1);
  if (right > pivot)
    q_sort(a, pivot+1, right);
}
//******************************************************************************
//********************************QUICK END*************************************
//******************************************************************************

//******************************************************************************
//***********************************HEAP START*********************************
//******************************************************************************
int heapify(int a[],int array_size)
{

    int start= (array_size- 2) / 2;
    for(; start >= 0; start--)     
    {
     siftDown(a, start, array_size-1);
     }
     return 0;
}
int siftDown(int a[], int start,int end)
{
    int root;
    int child;
    root=start;
    while (root * 2 <= end)
    {
          if (root*2 == end)
			child = root * 2;
		else if(a[root * 2] > a[root * 2 + 1])
			child = root * 2;		
		else
			child = root * 2 + 1;


		if(a[root] < a[child])
		{
			swap(a[root], a[child]);
			root = child;
		}
		else
			return 0;
   }
}
int heapSort(int a[], int array_size)
{
  long int start, end;
  start= clock();
      int i;
            
	heapify(a, array_size);
	

	for (end = array_size - 1; end >= 1; end--)
	{
		swap(a[end], a[0]);
		siftDown(a, 0, end - 1);		
	}
end= clock();
outf<<(end-start)/CLOCKS_PER_SEC<<"    "<<endl<<endl;
      for(i=0; i<array_size; i++)
      cout<<setw(7)<<a[i];
      cout<<endl<<endl;
}


//******************************************************************************
//***********************************HEAP END***********************************
//******************************************************************************


//COPY START
void copy(int array1[], int size)
{
      int array2[size];
      for(int i=0; i < size; ++i)
      array2[i] = array1[i];
      return;
}

its still not completely right,it posts the times as all zeros.if anyone knows what wrong with this.i could use the help.

**anon** · 05-04-2009

You are now copying to a local array which will be gone when the copy function finishes.

When you look at the signature of the copy function, you can read it as "copy size elements from array1 to ...?"

**iMalc** · 05-04-2009

Originally Posted by kakashi316

so it should be

Code:

void copy(int copiedarray[],int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                copiedarray[arraysize]=numbers[arraysize];   
                }
     return 0;
}

Almost. You shouldn't have a return statement in that function, and I'd sooner see those for-loop braces gone than left using that horrible indentation style. So yeah I really did literally mean just two lines in the function body.
Lack of a space after a comma also irritates me.

This other one you've now posted with a signature of

Code:

void copy(int array1[], int size)

is wrong for about 3 different reasons. But at least it has the space after the comma

**kakashi316** · 05-04-2009

Im still having trouble getting times other than zero to print.I believe that my copy function is still not right,though i have modified it to what you guys have been telling me.if anyone can help me get rid of this problem once and for all i would be appreciative

Code:

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<fstream>
using std::rand;
using std::srand;
using namespace std;
//FUNCTIONS START***************************************************************
int BubbleSort(int numbers[],int arraysize);
int insertion_sort(int numbers[], int arraysize);
int quickSort(int numbers[], int array_size);
int q_sort(int a[], int left, int right);
int heapSort(int numbers[], int array_size);
int heapify(int numbers[],int array_size);
int siftDown(int numbers[], int start,int end);
void copy(int copiedarray[], int numbers[],int arraysize);
//FUNCTIONS END*****************************************************************
ofstream outf("f:Proj3-Output.dat", ios::out);
ifstream inf("f:Proj3-input.dat", ios::in);
//******************************************************************************
//**********************************MAIN****************************************
//******************************************************************************
int main()
{
     float t1, t2, t3, t4;
     int array_cnt;          
     int results1;
     int results2;
     int results3;
     int results4;
     int x_1, x_2;
     srand(time(0));
     int arraysize = 10000;
     int numbers[arraysize];
     int copiedarray[arraysize];
     for (int i = 0; i < arraysize; i++)   
     numbers[i] = 1+ rand() % 100000;

     
outf<<"SIZE   "<<"QUICK "<<"HEAP "<<"BUBBLE "<<"INSERTION "<<endl;      
for (int global=1; global<=20; global++)
{    
for (int i = 0; i < arraysize; i++)
                {   
               arraysize=arraysize+1500;
                 array_cnt++;    
                } 
copy(copiedarray,numbers,arraysize);
results1=BubbleSort(copiedarray,arraysize);

copy(copiedarray,numbers,arraysize);
results2=insertion_sort(copiedarray, arraysize);

copy(copiedarray,numbers,arraysize);
results3=quickSort(copiedarray, arraysize);

copy(copiedarray,numbers,arraysize);
results4=heapSort(copiedarray, arraysize);                                                          

}         
         return 0;

}    

//******************************************************************************
//********************************** END OF MAIN********************************
//******************************************************************************

//******************************************************************************
//********************************BUBBBLE START*********************************
//******************************************************************************

int BubbleSort(int a[], int array_size)
{    
  long int start, end;
  start= clock();  
     int i, j, temp;
     for (i = 0; i < (array_size - 1); ++i)
     {
          for (j = 0; j < array_size - 1 - i; ++j )
          {
               if (a[j] > a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }
end= clock();
outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
     for(i=0; i<array_size; i++)
     cout<<setw(7)<<a[i];
}

//******************************************************************************
//********************************BUBBBLE END***********************************
//******************************************************************************

//******************************************************************************
//******************************INSERTION START*********************************
//******************************************************************************
int insertion_sort(int a[], int array_size)
{
  long int start, end;
  start= clock();
     int i, j, key;
     for(j = 1; j < array_size; j++)    //Notice starting with 1 (not 0)
    {
           key = a[j];
           for(i = j - 1; (i >= 0) && (a[i] > key); i++)   //Move smaller values up one position
          {
                 a[i+1] = a[i];
          }
         a[i+1] = key;    //Insert key into proper position
     }
end= clock();
outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
     for(i=0; i<array_size; i++)
     cout<<setw(7)<<a[i];
}
//******************************************************************************
//********************************INSERTION END*********************************
//******************************************************************************

//******************************************************************************
//**********************************QUICK START*********************************
//******************************************************************************
int quickSort(int a[], int array_size)
{
  long int start, end;
  start= clock();
  int i;
  q_sort(a, 0, array_size - 1);
  end= clock();
  outf<<(end-start)/CLOCKS_PER_SEC<<"    ";
  for(i=0; i<array_size; i++)
  cout<<setw(7)<<a[i];
}

int q_sort(int a[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = a[left];
  while (left < right)
  {
    while ((a[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      a[left] = a[right];
      left++;
    }
    while ((a[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      a[right] = a[left];
      right--;
    }
  }
  a[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(a, left, pivot-1);
  if (right > pivot)
    q_sort(a, pivot+1, right);
}
//******************************************************************************
//********************************QUICK END*************************************
//******************************************************************************

//******************************************************************************
//***********************************HEAP START*********************************
//******************************************************************************
int heapify(int a[],int array_size)
{

    int start= (array_size- 2) / 2;
    for(; start >= 0; start--)     
    {
     siftDown(a, start, array_size-1);
     }
     return 0;
}
int siftDown(int a[], int start,int end)
{
    int root;
    int child;
    root=start;
    while (root * 2 <= end)
    {
          if (root*2 == end)
			child = root * 2;
		else if(a[root * 2] > a[root * 2 + 1])
			child = root * 2;		
		else
			child = root * 2 + 1;


		if(a[root] < a[child])
		{
			swap(a[root], a[child]);
			root = child;
		}
		else
			return 0;
   }
}
int heapSort(int a[], int array_size)
{
  long int start, end;
  start= clock();
      int i;
            
	heapify(a, array_size);
	

	for (end = array_size - 1; end >= 1; end--)
	{
		swap(a[end], a[0]);
		siftDown(a, 0, end - 1);		
	}
end= clock();
outf<<(end-start)/CLOCKS_PER_SEC<<"    "<<endl<<endl;
      for(i=0; i<array_size; i++)
      cout<<setw(7)<<a[i];
      cout<<endl<<endl;
}


//******************************************************************************
//***********************************HEAP END***********************************
//******************************************************************************


//COPY START
void copy(int copiedarray[], int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                copiedarray[arraysize]=numbers[arraysize];   
                }
}

**anon** · 05-04-2009

Code:

//COPY START
void copy(int copiedarray[], int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                copiedarray[arraysize]=numbers[arraysize];   
                }
}

See anything wrong there? What is even the purpose of the loop if you always access the same item (which is out of bounds in the first place)?

**kakashi316** · 05-04-2009

Is this right or am i completely far off? Have paitence with me im that bad at programming.

Code:

void copy(int copiedarray[], int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                copiedarray[arraysize]=numbers[arraysize];
                cout<<copiedarray[arraysize];   
                }
}

**kakashi316** · 05-04-2009

somebody help me,im major league desperate to get this working.

**anon** · 05-04-2009

So does it produce the expected output? Does it crash?

I already pointed out that the red line is not correct. What is the purpose of accessing the same invalid indexes over and over in a loop?

**iMalc** · 05-04-2009

Originally Posted by anon

Code:

//COPY START
void copy(int copiedarray[], int numbers[],int arraysize)
{
     for (int i = 0; i < arraysize; i++)
                {   
                copiedarray[arraysize]=numbers[arraysize];   
                }
}

See anything wrong there? What is even the purpose of the loop if you always access the same item (which is out of bounds in the first place)?

Doh, sometimes it's hard to see a bug I would probably never make myself.

Hint: Which position in the array is it copying, and shouldn't it be a different position each time?!

Thread: sorting array/copying

Thread Tools

Search Thread

Display

sorting array/copying

something new.....

Similar Threads

Need help with linked list sorting function

Sorting Algorithm Help

sorting structure members using pointers

Still Needing Help : selection sorting

selection sorting