Программа JavaScript для проверки того, отсортирован ли массив или нет

В этой статье мы узнаем, как проверить, отсортирован ли массив в JavaScript. JavaScript Array — это одна переменная, которая используется для хранения элементов разных типов данных. Теперь нам нужно выяснить, отсортирован ли массив или нет.

Примеры:

Input : const arr = [1, 2, 3, 4, 5]; 
Output : true

Input : const arr = [3, 1, 4, 2, 5];
Output : false

Ниже приведены следующие подходы, с помощью которых мы можем проверить, отсортирован массив или нет:

• Использование подхода грубой силы
• Использование every()метода
• Использование метода сортировки()
• Использование метода рекурсии

Подход 1: Использование метода грубой силы

В этом подходе мы перебираем массив и сравниваем каждый элемент со следующим. Если первый элемент больше следующего, мы возвращаем false, иначе возвращаем true.

Пример:

Javascript

function checkSorted(arr) {

    for (let i = 0; i < arr.length - 1; i++) {

        if (arr[i] > arr[i + 1]) {

            return false;

        }

    }

    return true;

}

 

// Example usage

const arr1 = [32, 39, 48, 56];

const arr2 = [22, 65, 1, 39];

 

console.log(checkSorted(arr1));   

console.log(checkSorted(arr2));

Выход

true
false

Временная сложность: O(n)
Вспомогательное пространство: O(1)

Подход 2: Использование методаevery()

Это тоже своего рода итеративный метод, но в этом подходе мы используем метод Every() для итерации вместо цикла for. В JavaScript имеется множество встроенных методов. Метод Javascript Array.every() рассматривает все элементы массива, а затем дополнительно проверяет, удовлетворяют ли все элементы массива заданному условию (переданному пользователем) или нет, которое предоставляется методом, переданным ему в качестве аргумента..

Пример:

Javascript

function checkSorted(arr) {

    return arr.every((value, index, array) => 

                     index === 0 || value >= array[index - 1]);

}

// Example usage

const arr1 = [32, 39, 48, 56];

const arr2 = [22, 65, 1, 39];

 

console.log(checkSorted(arr1));

console.log(checkSorted(arr2));

Выход

true
false

Временная сложность: O(nlogn)
Вспомогательное пространство: O(1)

Подход 3. Использование метода sort()

Это также очень простой метод, но он не оптимизирован. В этом методе мы сортируем массив, используя встроенный метод JavaScript sort(), а затем сравниваем с исходным массивом, равны ли оба массива. Если они равны, то массив сортируется.

Пример:

Javascript

function checkSorted(arr) {

    const sortArr = [...arr].sort((a, b) => a - b);

    return JSON.stringify(arr) === JSON.stringify(sortArr);

 

}

 

// Example usage

const arr1 = [32, 39, 48, 56];

const arr2 = [22, 65, 1, 39];

 

console.log(checkSorted(arr1));

console.log(checkSorted(arr2));

Выход

true
false

Временная сложность: O(nlogn)
Вспомогательное пространство: O(n)

Подход 4: Использование рекурсии

• Если мы достигнем конца массива, он будет отсортирован, это базовый случай рекурсии.
• Теперь проверьте, больше ли текущий элемент, чем следующий, и верните false.
• В противном случае вызовите рекурсивную функцию для следующей пары элементов.

Пример:

Javascript

function checkSorted(arr, i = 0) {

    //base case

    if (i === arr.length - 1) {

        return true;

    }

    if (arr[i] > arr[i + 1]) {

        return false;

    }

 

    // Recursive case

    return checkSorted(arr, i + 1);

}

// Example usage

const arr1 = [32, 39, 48, 56];

const arr2 = [22, 65, 1, 39];

 

console.log(checkSorted(arr1));

console.log(checkSorted(arr2));

Выход

true
false