Упорядочить массив, пока пользователь вводит значение каждой позиции массива

Question

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

Дело в том, что я хочу избежать попыток использовать метод "bubble" или "quick sort".

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

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", &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).

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

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

Answer 1

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

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

1. Массив отсортирован от индекса 0 до индекса i-1
2. И у вас есть новый номер, список [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", &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 && 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.)

Answer 2

Если вы хотите избежать пузырьковой сортировки или вставки, вы можете просто вызвать сортировку слиянием после каждого ввода.Это сделало бы всю вашу программу 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.