Блог

Я пытаюсь упорядочить значения массива, пока пользователь вводит его значения.

Дело в том, что я хочу избежать попыток использовать метод «пузырь» или «быстрая сортировка».

Вот мой код и как он работает:

 int i, j, k;
      int number;
      for (i = 0; i < size; i = i   1) {
          printf("Give me the number #%d to add to the list: ", i   1);
          while (!scanf("%d", amp;list[i])) {
            while(getchar() != 'n');
            printf("You can't use chars!.n");
            printf("Give me the number #%d to add to the list: ", i   1);
          }
          number = list[i];
          if (number < list[i-1]) {
            list[i-1] = list[i];
            list[i] = number;
          }
      }
      for (i = 0; i < size; i = i   1) {
        printf("%d,", list[i]);
      }
  

что я получаю:

 How much numbers do you want to order? 5
Give me the number #1 to add to the list: 5
Give me the number #2 to add to the list: 4
Give me the number #3 to add to the list: 3
Give me the number #4 to add to the list: 2
Give me the number #5 to add to the list: 1
4,3,2,1,1,% // here is the problem, the expected output should be: 1,2,3,4,5 (for example, if I have 5,8,3,2,9 I should get: 2,3,5,8,9).
  

Я был бы признателен за объяснение того, почему мой код не работает, и, если возможно, за рекомендацию о том, как визуализировать подобные проблемы в будущем.

Заранее спасибо за помощь.

Чтобы сохранить сортировку массива, вы должны выполнить (частичную) сортировку вставки для каждого введенного числа.

Просто напоминая вам об алгоритме сортировки по вставке, он выполняет следующее для i-й итерации:

1. Массив сортируется с индекса 0 до индекса i-1
2. И у вас есть новый номер, list[i].
3. Вы должны определить, где это новое число помещается в массиве, поэтому вы сдвигаете числа назад, пока не увидите, куда подходит новое число.
4. Как только вы увидите число, которое не больше нового, теперь вы можете поместить новое сразу после этого числа.

Проблема с вашим кодом заключается в том, что вы неправильно сдвигаете.

Вы должны переместить все числа, которые больше нового числа, в конец, чтобы освободить место для нового. Но ваш код сдвигает только последнее число.

     int i, j, k;
    int number;
    for (i = 0; i < size; i = i   1)
    {
        printf("Give me the number #%d to add to the list: ", i   1);
        while (!scanf("%d", amp;list[i]))
        {
            while (getchar() != 'n')
                ;
            printf("You can't use chars!.n");
            printf("Give me the number #%d to add to the list: ", i   1);
        }
        number = list[i];

        /* Here's the point! Shift all numbers bigger than *number* to the back. */
        for (j = i; j > 0 amp;amp; number < list[j - 1]; j--)
        {
            list[j] = list[j - 1];
        }
        list[j] = number;
    }
    for (i = 0; i < size; i = i   1)
    {
        printf("%d,", list[i]);
    }

  

(Извините за переформатирование, это просто то, что делает моя IDE.)

Если вы хотите избежать сортировки пузырьками или вставки, вы можете просто вызвать сортировку слиянием после каждого ввода. Это сделало бы всю вашу программу O (x * nlogn), где n log n — время выполнения вашей сортировки слиянием, а x — время выполнения вашего цикла ввода.

Проблема с вашей текущей реализацией заключается в том, что она неправильно упорядочивает оставшиеся элементы. Представьте следующее:

 user inputs 2 --> array now has = [2]
user inputs 7 --> array now has = [2, 7] 
user inputs 3 --> array now has = [2, 3, 7]
  

Вы видите, как этот массив помещает 3 прямо посередине между 2 и 7? Это означает, что при сортировке также должны быть перемещены все элементы, сдвинутые вправо.

Ваша текущая реализация этого не делает. Вместо этого ваша реализация сдвигает элементы слева направо только один раз.

Что еще хуже, ваша реализация ограничена вашим циклом ввода. Это означает, что вы сортируете массив только в пределах очень определенного локального диапазона, который ограничен вашим циклом ввода. Вместо сортировки массива, в пределах фактического диапазона массива.

Что произойдет, если пользователь введет следующие числа: 2, 7, 4, 1? В вашем цикле отсутствует первый индекс, поэтому 1 сравнивается только со значениями 7 и 4.