Thread: Array sort exception return

i am creating 5 deferent tables each one has 20000 more elements more than the previous when i try to sort them with the sort algorithm quick sort for the first table tha has 20000 elements runs grate then it throws this exception how is this fixable ? exception : terminate called after throwing an instanceof 'std::bad_alloc' this application has Requested the Runtime to terminate it in an unusual way. Please contact the applications's support team for more information. Process returned 255(0xFF) . here is the code that gives this return :

Code:

Code:

#include<time.h>
#include<stdlib.h>
#include <string.h>
#include <ctime>
using namespace std;
int * Create_Table(int table[],int N);
void Quic_kSort(int arr[], int left, int right);
int main()
{
for (int N=20000; N<=100000; N=N+20000)
{
//clock_t begin = clock();
int *table = new int32_t [N];
table=Create_Table(table,N);
Quic_kSort(table,0,N);
system("pause");
cout << endl;
clock_t end = clock();
//double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
//cout << "The elapsed time for N : "<<N<< " elements is : "<<elapsed_secs<<endl;
//delete table;
}

}
int * Create_Table(int table[],int N)
{
srand(time(NULL));
    for (int i=0; i<N; i++)
        table[i]= rand()%150000;
return table;

}

 void Quic_kSort(int arr[], int left, int right)
 {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
    }
}
/* recursion */
if (left < j)
    Quic_kSort(arr, left, j);
if (i < right)
        Quic_kSort(arr, i, right);
}

i dont want to use vector i want to use pointers in this ocaision i tryied the delete too but it doesnt work it gives the same error is it possible to run out of memmory? that simple....

Originally Posted by laserlight

That is what std::bad_alloc is hinting at. You might still have available memory, but not contiguously large enough.

Isn't this using a virtual address space? If so, then the physical pages can be scattered, only the virtual address space needs to be contiguous. In some cases, physical pages could end up being partially used due to many allocate and free operations on many different variables, but since only table is being allocated and freed, it shouldn't be an issue. It seems more likely that a mismatch in new ...[] and delete[] or not using [] on the delete could be the issue. As you mentioned, a one time allocation of table for the max size would be better.

Originally Posted by Elysia

You can still get fragmented virtual memory. If the operating system can't find a large enough contiguous virtual memory section, it will fail.

True in some cases, but if the example code is fixed, then the current array is freed before a new instance is allocated, so the virtual address space should also be freed up before it get's reallocated. As laserlight mentioned, it would be better to do a one time allocation of the max size array.

so how can i add the memory dynamical ? without new and delete [] ?
for instance : table = table + new int [20000];

What laserlight suggested is that you create table just one time before the loop:

Code:

// ...
    int *table = new int[100000];
    for (int N=20000; N<=100000; N=N+20000)
// ...
    delete[] table;

thanks allot all of you ,you were really helpful i really improve my code with your advises ,and also made my code work property