Как проверить, отсортирован ли массив из целых чисел в порядке возрастания?

Question

[X_Chyaka_X]

Вот мой код. С положительными числами работает, но если внести в массив отрицательные или 0, то даже если массив отсортирован в порядке возрастания - пишет, что не отсортирован.

#include <stdio.h>
#define TRUE 1
#define FALSE 0

int main()
{
    int i, j, size, cum ;
    printf("Vvedite kol-vo elementov massiva: ");
    scanf("%d", &size);
    int array[size];
    printf("Vvedite elementi massiva: \n");
    for (int i = 1; i<=size; i++) {
        scanf("%d", &array[i]);
    }
    for (int i = 1; i<=size; i++) {
        j = i-1;
        if (array[i] > array[j])
            cum = TRUE;
        else {
            cum = FALSE;
            break;
        }
    }
    if (cum == FALSE){
        printf("Массив не отсортироaан\n");
    }
    else {
         printf("Массив отсортирован\n");
    }
}

Comments

[Василий Банников]

1. Поправь форматирование. Невозможно читать же
Вообще, чтобы проверить, что массив отсортирован по возрастанию - тебе нужно просто убедиться, что каждый элемент массива больше либо равен элементу, идущему перед ним.

Answer 1

[Василий Банников]

Типа такого:

Моя оригинальная версия

#define TRUE 1;
#define FALSE 0;

int is_ordered(int* array, int size) {
  // Считаем, что пустой массив или массив из одного элемента - это отсортированный массив
  if (size <= 1)
    return TRUE;
  int previous = array[0];
  for(int i = 1; i < size; i++) { // самый первый элемент мы пропускаем
    int current = array[i];
    if (current < previous)
      return FALSE;
    previous = current;
  }
  return TRUE;
}

UPD: после рефакторинга Wataru

#define TRUE 1;
#define FALSE 0;

int is_ordered(int* array, int size) {
  for(int i = 1; i < size; i++) {
    if (array[i] < array[i-1]) return FALSE;
  }
  return TRUE;
}

Comments

[mayton2019]

+1 но добавлю свой копейка.

Меня всегда раздражало (в моем коде тоже) "трекание" предыдущего состояния цикла. Лет 5 назад я стал интересоваться ФП и там есть такое решение как zip одной коллекции самой с собой со сдвигом в 1 элемент. После такого сдвига подсчет превращается в достаточно плоскую формулу типа stream-pipeline.

Возможно удастся красиво это записать на C++20/Boost.

[Wataru]

Проще же тупо обращаться к (i-1)-ому элементу. Отсюда кстати понятнее, почему цикл надо с 1 гнать, а не с 0. И граничные условия проверять не надо. Если массив из 1 элемента, то цикл не выполнится ни разу.

int is_ordered(int* array, int size) {
  for(int i = 1; i < size; i++) {
    if (array[i] < array[i-1]) return FALSE;
  }
  return TRUE;
}

[Василий Банников]

mayton2019, ну в вопросе упоминается C, а не C++, так что буст и c++/20 точно мимо :)

[mayton2019]

Wataru, да согласен. Но в некой "итераторной" постановке нам нужно будет просто видеть текущий элемент и предыдущий. А никаких индексов нет. Впрочем это я фантазирую. Можно забить на это.

[Василий Банников]

mayton2019, или можно использовать скользящее окно.

[Wataru]

mayton2019, Ну это же Си. И тем более человек его явно еще только учит. Так что выкручивать всякие парадигмы, подходы и абстракции - не самая лучшая идея в этом вопросе. Тут чем проще код, тем лучше, по-моему.

[mayton2019]

Или в некой математической форме. Если массив это функция от индекса элемента - то доказать что все первые производные в точках - неотрицательные.

[mayton2019]

Василий Банников,

скользящее окно

. Окно. Форточка. Как будет угодно. В данном случае
эта метафора тоже лежит вне плоскости языка Си. И мы читая глазами код не может точно сказать окно тут или не окно. В противоположность в SQL есть коробочные окнонные функции которые если есть то уж точно есть.

Answer 2

[Владимир]

Для начала разберитесь с массивами.
Адресация от 0 до N-1 (где N исло элементов в массиве).
И с объявлением массива. Память под массив выделяется при компиляции, если требуется определить размер массива при выполнении - используйте функции выделения памяти типа maloc().