我生成随机数的函数不会超过 500000

Question

我会直接解决我的问题。所以基本上我想做的是生成一组不同数量的随机数。所以一个有 10,000、50,000、100,000、500,000、600,000 等。然后我会使用快速排序对它们进行排序，并将排序后的数组打印到屏幕上。此外，它到达运行所花费的时间也将被记录和打印。然而，我唯一遇到问题的部分是生成数组。出于某种原因，生成超过 500,000 个随机数不起作用，returns this:

进程在 2.112 秒后退出，return 值为 3221225725

按任意键继续。 . . ([1]: https://i.stack.imgur.com/m83el.png)

这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void randNums(int array[], int range) {
    int i, num;
    for (i = 0; i < range; i++) {
        num = rand() % range;
        array[i] = num;
    }
}

//prints elements of given array
void display(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("#%d. %d\n", i, array[i]);
    }
}

//displays time taken for sorting algorithm to run
void timeTaken(char sortingAlgo[], int size, clock_t start, clock_t end) {
    double seconds = end - start;
    double milliseconds = seconds / 1000;
    printf("Time taken for %s Sort to sort %d numbers was %f milliseconds or %f seconds",
           sortingAlgo, size, milliseconds, seconds);       
}
 
//quick sort
void quickSort(int array[], int first, int last) {
    int i, j, pivot, temp;
    if (first < last) {
        pivot = first;
        i = first;
        j = last;
        while (i < j) {
            while (array[i] <= array[pivot] && i < last)
                i++;
            while (array[j] > array[pivot])
                j--;
            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        temp = array[pivot];
        array[pivot] = array[j];
        array[j] = temp;
        quickSort(array, first, j - 1);
        quickSort(array, j + 1, last);
    }
}

int main() { 
    int size = 600000;
    int myArray[size];
    time_t end, start;
    int first, last;

    randNums(myArray, size);    
    first = myArray[0];
    last = sizeof(myArray) / sizeof(myArray[0]);
    
    time(&start);
    quickSort(myArray, first, last);
    time(&end); 
    display(myArray, size);
    timeTaken("Quick", size, start, end);

    return 0;
}

任何帮助将不胜感激，谢谢！

Answer 1

这段代码中有很多不难解决的小错误。我将在此重构和清理中尝试将其分解：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void randNums(int* array, int range) {
  // Declare iterator variables like `i` within the scope of the iterator.
  for (int i = 0; i < range; i++) {
    // No need for a single-use variable here, just assign directly.
    array[i] = rand () % range;
  }
}

void display(int* array, int size) {
  // for is not a function, it's a control flow mechanism, so
  // it is expressed as `for (...)` with a space. `for()` implies
  // it is a function, which it isn't.
  for (int i = 0; i < size; i++) {
    printf("#%d. %d\n", i, array[i]);
  }
}

void timeTaken(char* sortingAlgo, int size, clock_t start, clock_t end) {
  // Time calculation here needs to account for the fact that clock_t
  // does not use seconds as units, it must be converted
  // https://en.cppreference.com/w/c/chrono/clock_t

  printf(
    "Time taken for %s Sort to sort %d numbers was %.6f seconds",
    sortingAlgo,
    size,
    ((double) (end - start)) / CLOCKS_PER_SEC
  );
}

void quickSort(int* array, int first, int last) {
   // Establish a guard condition. Rest of the function is no longer
   // nested in a control flow structure, so it simplifies the code.
   if (first >= last) {
     return;
   }

  int pivot = first;
  int i = first;
  int j = last;

  // Use `while (...)` as it's also a control flow structure.
  while (i < j) {
    // Adding space around operators improves clarity considerably. Unspaced
    // elements like `a->b()` are supposed to stand out and not be confused
    // with visually similar `a>>b()` which does something very different.
    while (array[i] <= array[pivot] && i < last) {
      i++;
    }

    // Use surrounding braces on all blocks, even single-line ones, as this
    // can avoid a whole class of errors caused by flawed assumptions.
    // while (...) { ... }
    while (array[j] > array[pivot]) {
      j--;
    }

    if (i < j) {
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
  }

  int temp = array[pivot];
  array[pivot] = array[j];
  array[j] = temp;

  quickSort(array, first, j - 1);
  quickSort(array, j + 1, last);
}

int main(int argc, char** argv) {
  int size = 600000;

  // If an argument was given...
  if (argc > 1) {
    // ...use that as the size parameter instead.
    size = atol(argv[1]);
  }

   // Allocate an array of sufficient size
  int* numbers = calloc(size, sizeof(int));

  randNums(numbers, size);

  // time_t has at best second-level precision, it's very inaccurate.
  // Use clock_t which gives far more fidelity.
  clock_t start = clock();

  // This function takes *offsets*, not values.
  quickSort(numbers, 0, size - 1);

  clock_t end = clock();

  display(numbers, size);

  timeTaken("Quick", size, start, end);

  free(numbers);

  return 0;
}

这里的第一个错误是错误地调用了 quickSort()：

// Represents first *value* in the array
first = myArray[0]; // Should be: 0

// Rough calculation of the size of the array, but this is off by one
last = sizeof(myArray)/sizeof(myArray[0]); // Should be: size - 1
    
quickSort(myArray, first, last);

我生成随机数的函数不会超过 500000

My function for generating random numbers isn't going past 500000

c

arrays

random

numbers

data-structures