Я использую счетную сортировку для сортировки выбранных чисел из файла.Похоже, это работает нормально для файлов без повторяющихся записей, но как только появляются дубликаты, начинает появляться множество нулей.
1612 1894 3018 4212 6046 12894 13379 14408 14615 16394 17982 23004 27588 31393 33195 39526 54326 54566 67926 72479 * 966 157832 7039081011 *
Вывод:
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;
}