对具有重复条目的列表进行计数排序奇数结果

Question

我正在使用计数排序来对从文件中读取的数字选择进行排序。这对于没有重复条目的文件似乎工作得很好，但是一旦有重复，就会开始出现大量的零。

您知道为什么会发生这种情况以及如何解决它吗？

示例:

输入(不重复):

1612 1894 3018 4212 6046 12894 13379 14408 14615 16394 17982 23004 27588 31393 33195 39526 54326 54566 67926 72479 90466 157832 703908

输出:

0: 1612 1: 1894 2: 3018 3: 4212 4: 6046 5: 12894 6: 13379 7: 14408 8: 14615 9: 16394 10: 17982 11: 23004 12: 27588 13: 31393 14: 33195 15: 39526 16: 54326 17: 54566 18: 67926 19: 72479 20: 90466 21: 157832 22: 703908

输入(有重复项):

1612 1894 3018 4212 6046 12894 13379 14408 14615 16394 17982 23004 27588 31393 33195 39526 54326 54566 60000 60000 60000 60000 703908

输出(参见 18++):

0: 1612 1: 1894 2: 3018 3: 4212 4: 6046 5: 12894 6: 13379 7: 14408 8: 14615 9: 16394 10: 17982 11: 23004 12: 27588 13: 31393 14: 33195 15: 39526 16: 54326 17: 54566 18: 0 19: 0 20: 0 21: 60000 22: 60000

输入:

2 2 2 2 2 3 3 3 3 3

输出:

0: 119 1: 110 2: 2025792 3: 3249376 4: 56 5: 2 6: 2 7: 2 8: 2 9: 2

用于生成此输出的代码片段:

int *numbers = (int *) calloc(rows, sizeof(int));

int i = 0;
int max = -1; //min
int min = 500000000; //max
while(fscanf(inputPtr, "%d", &numbers[i]) != EOF) {
  //printf("%d\n", numbers[i]);
  if(numbers[i]>max) max = (int) numbers[i];
  if(numbers[i]<min) min = (int) numbers[i];
  i++;
}

countingSort(numbers, rows, max, min);

void countingSort(int array[], const int end, const int max, const int min) {
  int i;
  const int range = max-min+1;
  int count[range+1],
      scratch[end];

  for(i=0; i<range+1; i++)
    count[i] = 0;

  /* Set the value of count[i] to the number of
   * elements in array with value i+min-1. */
  for(i=0; i<end; i++) {
    int c = array[i]-1-min;
    count[c]++;
  }

  /* Update count[i] to be the number of
   * elements with value less than i+min. */
  for(i=1; i<range; i++)
    count[i] += count[i-1];

  /* Copy the elements of array into scratch in
   * stable sorted order. */
  for(i=(end-1); i>=0; i--) {
    int c = array[i]-min;
    int s = count[c];
    scratch[s] = array[i];
    /* Increment count so that the next element
     * with the same value as the current element
     * is placed into its own position in scratch. */
    count[c]++;
  }

  for(i=0; i<end; i++)
    array[i] = scratch[i];
}

<小时/>

完整代码:

#include <stdio.h>  // FILE stderr fopen fclose fprintf printf fgets
#include <stdlib.h> // Standard Lib :-)
#include <math.h> // Every body was kung fu math

/**
 * Given any number of program parameters (command-line parameters)
 * calculates the length of each one, and writes the longest to standard output
 * this time using counting sort!
 */

/*
 * Output the usage
 */ 
void usage () {
  printf("Usage:\n"
         "Usage: part2 rows fileToRead\n");
}

/**
 * counting sort
 * http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Counting_sort
 */
void countingSort(int array[], const int end, const int max, const int min) {
  int i;
  const int range = max-min+1;
  int count[range+1],
      scratch[end];

  for(i=0; i<range+1; i++)
    count[i] = 0;

  /* Set the value of count[i] to the number of
   * elements in array with value i+min-1. */
  for(i=0; i<end; i++) {
    int c = array[i]-1-min;
    count[c]++;
  }

  /* Update count[i] to be the number of
   * elements with value less than i+min. */
  for(i=1; i<range; i++)
    count[i] += count[i-1];

  /* Copy the elements of array into scratch in
   * stable sorted order. */
  for(i=(end-1); i>=0; i--) {
    int c = array[i]-min;
    int s = count[c];
    scratch[s] = array[i];
    /* Increment count so that the next element
     * with the same value as the current element
     * is placed into its own position in scratch. */
    count[c]++;
  }

  for(i=0; i<end; i++)
    array[i] = scratch[i];
}

/**
 * return the appropriate percentile
 */
int getPercentile(double percent, int *array, int array_size) {
  int number = (floor(percent*array_size)+1); //-1 for arrays

  //Make number suitable for arrays
  number -= 1;

  //printf("%d\n", number);

  //Ensure the numbers aren't the same
  while(array[number-1]==array[number]) {
    number++;

    if(number>=array_size)
      return -1;
  }

  //printf("%d\n", number);

  return (int) array[number];
}

/**
 * The main method
 * part2 1000 datafile
 */ 
int main (int argc, char *argv[]) {
  //I need three args
  //1 rows
  //2 file name
  if(argc==3) {
    int rows = 0;     
    if(sscanf(argv[1], "%d", &rows) == 0) {
      printf("The number of rows must be a number.\n");
      usage();   
      exit(-1);       
    }

    FILE *inputPtr; //File pointers
    inputPtr = fopen(argv[2], "r"); //same as PHP ;-)

    // Sensible errors
    if(inputPtr==NULL) {
      printf("I could not open the file for input.\n");
      usage();
      exit(-1);
    }

    // Read all the numbers
    int *numbers = (int *) calloc(rows, sizeof(int));

    int i = 0;
    int max = -1; //min
    int min = 500000000; //max
    while(fscanf(inputPtr, "%d", &numbers[i]) != EOF) {
      //printf("%d\n", numbers[i]);
      if(numbers[i]>max) max = (int) numbers[i];
      if(numbers[i]<min) min = (int) numbers[i];
      i++;
    }

    printf("%d, %d, %d\n\n", min, max, rows);

    //int array[], const int end, const int max, const int min) {
    countingSort(numbers, rows, max, min);

    for(i = 0; i < rows; i++) {
      printf("%i: %d\n", i, numbers[i]);
    }  
    printf("-------\n\n");

    // Close the files
    //fclose(inputPtr);
    //not pointing to file anymore

    int percentile = getPercentile(0.9, numbers, rows);

    printf("%s: %d\n", argv[2], percentile);

  } else {
    printf("Please provide two CLI's!\n");
    usage();
    return 0;
  }


  /* All done */
  return 0;

}

Answer 1

这里有一个错误:

/* Set the value of count[i] to the number of
 * elements in array with value i+min-1. */
for(i=0; i<end; i++) {
    int c = array[i]-1-min;
    count[c]++;
}

如果注释正确，您应该设置c = array[i]+1-min;。没有其他东西跳出来。