Есть код, который выполняет сортировку подсчётом (что-то похожее на ключ-значение), но нужно исполнить 1 нюанс, при выполнении сортировки, нужно учитывать повторяющиеся элементы, то есть, если таковые имеются, то они должны оставаться в том же порядке Например:
- 1 5
- 4 5
- 1 3
- 3 4
Должен отсортировать как:
- 1 5
- 1 3
- 3 4
- 4 5
Прилагаю весь код (В том числе и функцию main()):
#include <stdio.h>
#include <stdlib.h>
void countingSort(int *a, int *def, int n)
{
int i;
int min, max;
int k;
int *c;
int *b;
int *d;
min = max = a[0];
for(i = 1; i < n; i++) {
if (a[i] < min) min = a[i];
else if (a[i] > max)
max = a[i];
}
k = max - min + 1;
c = (int*)malloc(k * sizeof(int));
b = (int*)malloc(n * sizeof(int));
d = (int*)malloc(n * sizeof(int));
for(i = 0; i < n; i++)
c[a[i] - min]++;
for(i = 1; i < k; i++)
c[i] += c[i-1];
for(i = 0; i < n; i++)
{
b[c[a[i]-min]-1] = a[i];
d[c[a[i]-min]-1] = def[i];
c[a[i]-min]--;
}
for(i = 0; i < n; i++)
{
a[i] = b[i];
def[i] = d[i];
}
free(b);
free(c);
free(d);
}
int main() {
FILE *fin = fopen("input.txt", "r");
FILE *fout = fopen("output.txt", "w");
unsigned int n;
fscanf(fin, "%d", &n);
int *a = (int*)malloc(n * sizeof(int));
int *b = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
fscanf(fin, "%i %i", &a[i], &b[i]);
countingSort(a, b, n);
for (int i = 0; i < n; i++)
fprintf(fout, "%i %i\n", a[i], b[i]);
fclose(fin);
fclose(fout);
return 0;
}