0

Есть код, который выполняет сортировку подсчётом (что-то похожее на ключ-значение), но нужно исполнить 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;
  }

1 ответ 1

0

Для сохранения порядка пройдите этот цикл в обратном направлении, тогда последний из элементов с ключом a[i] запишется в конец своего диапазона, край диапазона сдвинется влево и так далее

 for(i = n-1; i >=0; i--)
      {
          c[a[i]-min]--;
          b[c[a[i]-min]] = a[i];
          d[c[a[i]-min]] = def[i];
      }

Edit: Увидел, что декремент счётчика можно перенести в начало и избавиться от вычитания единицы

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.