As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/
Options

Last minute C++ problem need help on the quick

Raziel078Raziel078 Registered User regular
edited July 2008 in Help / Advice Forum
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

I would like to put something clever and about me but I fear my company will find it
Raziel078 on

Posts

  • Options
    TechnicalityTechnicality Registered User regular
    edited July 2008
    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".

    Technicality on
    handt.jpg tor.jpg

  • Options
    Raziel078Raziel078 Registered User regular
    edited July 2008
    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)

    Raziel078 on
    I would like to put something clever and about me but I fear my company will find it
  • Options
    bowenbowen How you doin'? Registered User regular
    edited July 2008
    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.

    bowen on
    not a doctor, not a lawyer, examples I use may not be fully researched so don't take out of context plz, don't @ me
  • Options
    Premier kakosPremier kakos Registered User, ClubPA regular
    edited July 2008
    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".

    Premier kakos on
  • Options
    Raziel078Raziel078 Registered User regular
    edited July 2008
    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;
    }

    Raziel078 on
    I would like to put something clever and about me but I fear my company will find it
  • Options
    Premier kakosPremier kakos Registered User, ClubPA regular
    edited July 2008
    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.

    Premier kakos on
  • Options
    Raziel078Raziel078 Registered User regular
    edited July 2008
    okay thats what I figured was wrong, but I'm unsure of how to correct this.

    Raziel078 on
    I would like to put something clever and about me but I fear my company will find it
  • Options
    BamaBama Registered User regular
    edited July 2008
    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.

    Bama on
  • Options
    SavantSavant Simply Barbaric Registered User regular
    edited July 2008
    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.

    Savant on
  • Options
    Raziel078Raziel078 Registered User regular
    edited July 2008
    I just finished presenting I'm gonna find out how I did though.

    Raziel078 on
    I would like to put something clever and about me but I fear my company will find it
Sign In or Register to comment.