Я думал о сортировке подсчетом и о том, как мы ее реализуем, на самом деле, как работает алгоритм. Я застрял с одной частью, алгоритм действительно прост и понятен, но одна его часть не кажется необходимой. Я думал, что люди могут ошибаться или около того, но похоже, что все используют один и тот же метод, поэтому я где-то ошибаюсь. Не могли бы вы объяснить.
Вот код для подсчета сортировки от geeksforgeeks
// C Program for counting sort
#include <stdio.h>
#include <string.h>
#define RANGE 255
// The main function that sort the given string arr[] in
// alphabatical order
void countSort(char arr[])
{
// The output character array that will have sorted arr
char output[strlen(arr)];
// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[RANGE + 1], i;
memset(count, 0, sizeof(count));
// Store count of each character
for(i = 0; arr[i]; ++i)
++count[arr[i]];
// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (i = 1; i <= RANGE; ++i)
count[i] += count[i-1];
// Build the output character array
for (i = 0; arr[i]; ++i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
// Copy the output array to arr, so that arr now
// contains sorted characters
for (i = 0; arr[i]; ++i)
arr[i] = output[i];
}
// Driver program to test above function
int main()
{
char arr[] = "geeksforgeeks";//"applepp";
countSort(arr);
printf("Sorted character array is %s\n", arr);
return 0;
}
Круто, но об этой части:
// Build the output character array
for (i = 0; arr[i]; ++i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
Зачем мне это?? Хорошо, я посчитал свои числа:
Допустим, у меня был массив -> [1, 3, 6, 3, 2, 4]
INDEXES 0 1 2 3 4 5 6
I created this -> [0, 1, 1, 2, 1, 0, 1]
Чем эта часть делает это:
[0, 1+0, 1+1, 2+2, 4+1, 0+5, 1+5]
[0, 1, 2, 4, 5, 5, 6]
НО ПОЧЕМУ ??
Разве я не могу просто использовать свой массив, как раньше? Вот моя идея и мой код, пожалуйста, объясните, почему это неправильно или почему другой способ более полезен.
void countingSort (int *arr) {
int countingArray[MAX_NUM] = {0};
for (i = 0 ; i < ARRAY_SIZE ; i++)
countingArray[arr[i]]++;
int output_Index = 0;
for (i = 0 ; i < MAX_NUM ; i++)
while ( countingArray[i]-- )
arr[output_Index++] = i;
}
