Last minute C++ problem need help on the quick

Raziel078

Okay here is my code it keeps saying that "expected constant expression cannot allocate an array of constant size 0 'matrix_A' : unknown size" I don't understand the problem as I'm asking for input before creating the matrix. should I change this to a function that I call to create the matrix? Here is my code

(removed code for space concerns)

what I need to do is create a program that will take an array and sort it using quick sort and heap sort and spit out times for each. I'm doing it piece by piece so I haven't added the timer yet. or the heap sort functions one problem at a time. Help

Technicality

Like it says, you are trying to initialise matrix_A with a number that is not a constant:

int matrix_A[inpt];

The compiler doesn't know what inpt is before the program is run.

If your array is not of a static size, you need to create it with "new" and remove it when you're done with "delete".

Raziel078

how do you do that.

EDIT: never mind its working now just took me a minute. Could you please hang out for a little bit as I am not quite done with this program yet? heres the code btw

(removed code to save room)

bowen

You may want to remove conio.h and change stdlib.h to cstdlib ; if you're using C++ (this causes some problems in some compilers), and you definitely don't need conio.h I'm betting. Just an FYI.

Premier kakos

Raziel078 wrote: »

int main() {
    
	int inpt;
    
    cout<<"Enter the size of the array to be sorted.";
    cin>>inpt;

    int matrix_A[inpt];
    for (int i=0; i<inpt; i++)
    {
        matrix_A[i]= (int) rand()&#37;99 ;
    }
  
  quickSort(matrix_A, 0, inpt-1);
  print(matrix_A);
  getch();
}

As someone pointed out, you can't declare a static matrix with a non-constant size. Here's how you fix it.

int main() {
  int inpt;
    
  cout<<"Enter the size of the array to be sorted.";
  cin>>inpt;

  int * matrix_A = new int[inpt];
  for (int i=0; i<inpt; i++)
  {
    matrix_A[i]= (int) rand()%99 ;
  }
  
  quickSort(matrix_A, 0, inpt-1);
  print(matrix_A);
  getch();

  delete [] matrix_A;
}

The new lines are:
"int * matrix_A = new int[inpt];"
This declares a pointer to an integer (arrays are pointers to their type, BTW) and then allocates space for 'inpt' number of ints and returns the pointer to the first one. At this point, matrix_A behaves just like your standard ol' array.

"delete [] matrix_A;"
Because you dynamically allocated the memory, you have to make sure to get rid of it at the end. That's what this line does. "delete [] <foo>;" is the syntax to delete an array allocated with "new".

Raziel078

okay I got my quick sort program to work. I'm working on my heap sort one and for some reason it can't handle more than like 100 variables. If I try 1000 or above it throws up and quits here is the code

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

double diffclock(clock_t clock1,clock_t clock2)
{
double diffticks=clock1-clock2;
double diffms=(diffticks*1000)/CLOCKS_PER_SEC;
return diffms;
}


void print(int a[], int hz) {
int heapSize = hz - 1;

for (int i = 0; i <= heapSize; i++) {
cout << a << "-";
}
cout << endl;
}

int parent(int i) {
if(i==1)
return 0;

if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}

int left(int i) {
return (2 * i);
}

int right(int i) {
return (2 * i) + 1;
}

void heapify(int a[], int i, int hz) {
int heapSize = hz;
int l = left(i), great;
int r = right(i);
if ( (a[l] > a) && (l < heapSize)) {
great = l;
}
else {
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize)) {
great = r;
}
if (great != i) {
int temp = a;
a = a[great];
a[great] = temp;
heapify(a, great, heapSize);
}
}

void BuildMaxHeap(int a[], int hz) {
int heapSize = hz;
for (int i = (heapSize - 1) / 2; i >= 0; i--) {
heapify(a, i, heapSize);
//print(a, heapSize);
}
}

void HeapSort(int a[],int hz) {
int heapSize = hz;
BuildMaxHeap(a, heapSize);
for (int i = heapSize; i > 0; i--) {
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize - 1;
heapify(a, 0, heapSize);
}

}

void main() {
time_t seconds;
seconds = time (NULL);
int inpt;

cout<<"Enter the size of the array to be sorted: ";
cin>>inpt;
cout<<"\n";

int* matrix_A = new int[inpt];
for (int i=0; i<inpt; i++)
{
matrix_A= (int) rand()%999 ;
}

char c[1000];
int tt;
clock_t begin=clock();

HeapSort(matrix_A, inpt);
clock_t end=clock();
cout << "Time elapsed: " << double(diffclock(end,begin)) << " ms"<< endl;

//print(matrix_A, inpt);
delete [] matrix_A;
system("PAUSE");
return 0;
}

Premier kakos

In heapify, it's segfaulting at this if statement:
"if ( (a[l] > a) && (l < heapSize))"

Specifically, when it crashes, 'l' is MUCH MUCH bigger than the heap size. In my particular example, I used a size of 10000 and 'l' was 19998. This happens even on smaller sizes, but on those smaller heaps, while you are trying to access a location outside of the array, it isn't outside of your segment, so it still continues on. It becomes a problem when the heap size is large enough such that the calculated 'l' value points to way outside of the heap.

Raziel078

okay thats what I figured was wrong, but I'm unsure of how to correct this.

Bama

In an "and" expression, if the left operand evaluates to false, the right operand is never tested. I haven't looked over your code in detail, but that seems like it might be useful with that problem.

Savant

To be more specific to the previous suggestions, you can either nest if statements or swap the two operands like so:
"if ( (l < heapSize) && (a[l] > a) )"

Here "a[l] > a" will not evaluate unless "l < heapSize" is true. In general, you want to be careful around arrays to not access them unless you have checked or are sure that your indices are within the bounds of the array. C/C++ allows you to shoot yourself in the foot by wandering out beyond the end of the array into mystery memory and will only crash right away if you are lucky.

Raziel078

I just finished presenting I'm gonna find out how I did though.