В этой статье мы узнаем, как проверить, отсортирован ли массив в 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