Dada una array de tamaño n , escriba un programa para verificar si está ordenado en orden ascendente o no. Se permiten valores iguales en una array y dos valores iguales consecutivos se consideran ordenados.
Ejemplos:
Input : 20 21 45 89 89 90 Output : Yes Input : 20 20 45 89 89 90 Output : Yes Input : 20 20 78 98 99 97 Output : No
Enfoque recursivo:
La idea básica para el enfoque recursivo:
1: If size of array is zero or one, return true. 2: Check last two elements of array, if they are sorted, perform a recursive call with n-1 else, return false. If all the elements will be found sorted, n will eventually fall to one, satisfying Step 1.
A continuación se muestra la implementación usando recursividad:
C++
// Recursive approach to check if an
// Array is sorted or not
#include <bits/stdc++.h>
using namespace std;
// Function that returns 0 if a pair
// is found unsorted
int arraySortedOrNot(int arr[], int n)
{
// Array has one or no element or the
// rest are already checked and approved.
if (n == 1 || n == 0)
return 1;
// Unsorted pair found (Equal values allowed)
if (arr[n - 1] < arr[n - 2])
return 0;
// Last pair was sorted
// Keep on checking
return arraySortedOrNot(arr, n - 1);
}
// Driver code
int main()
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = sizeof(arr) / sizeof(arr[0]);
if (arraySortedOrNot(arr, n))
cout << "Yes\n";
else
cout << "No\n";
}
Java
// Recursive approach to check if an
// Array is sorted or not
class CkeckSorted {
// Function that returns 0 if a pair
// is found unsorted
static int arraySortedOrNot(int arr[], int n)
{
// Array has one or no element or the
// rest are already checked and approved.
if (n == 1 || n == 0)
return 1;
// Unsorted pair found (Equal values allowed)
if (arr[n - 1] < arr[n - 2])
return 0;
// Last pair was sorted
// Keep on checking
return arraySortedOrNot(arr, n - 1);
}
// main function
public static void main(String[] args)
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = arr.length;
if (arraySortedOrNot(arr, n) != 0)
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Recursive approach to check if an
# Array is sorted or not
# Function that returns 0 if a pair
# is found unsorted
def arraySortedOrNot(arr):
# Calculating length
n = len(arr)
# Array has one or no element or the
# rest are already checked and approved.
if n == 1 or n == 0:
return True
# Recursion applied till last element
return arr[0] <= arr[1] and arraySortedOrNot(arr[1:])
arr = [20, 23, 23, 45, 78, 88]
# Displaying result
if arraySortedOrNot(arr):
print("Yes")
else:
print("No")
C#
// Recursive approach to check if an
// Array is sorted or not
using System;
class CkeckSorted {
// Function that returns 0 if a pair
// is found unsorted
static int arraySortedOrNot(int[] arr, int n)
{
// Array has one or no element or the
// rest are already checked and approved.
if (n == 1 || n == 0)
return 1;
// Unsorted pair found (Equal values allowed)
if (arr[n - 1] < arr[n - 2])
return 0;
// Last pair was sorted
// Keep on checking
return arraySortedOrNot(arr, n - 1);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 20, 23, 23, 45, 78, 88 };
int n = arr.Length;
if (arraySortedOrNot(arr, n) != 0)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Recursive approach to check if an
// Array is sorted or not
// Function that returns 0 if a pair
// is found unsorted
function arraySortedOrNot(arr, n)
{
// Array has one or no element or the
// rest are already checked and approved.
if (n == 1 || n == 0)
return 1;
// Unsorted pair found (Equal values allowed)
if (arr[n - 1] < arr[n - 2])
return 0;
// Last pair was sorted
// Keep on checking
return arraySortedOrNot(arr, n - 1);
}
// Driver code
let arr = [ 20, 23, 23, 45, 78, 88 ];
let n = arr.length;
if (arraySortedOrNot(arr, n) != 0)
document.write("Yes");
else
document.write("No");
// This code is contributed by sravan kumar G
</script>
Producción
Yes
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n) para pila de llamadas recursivas.
Otro enfoque recursivo:
C++
// C++ Recursive approach to check if an
// Array is sorted or not
#include <iostream>
using namespace std;
// Function that returns true if array is
// sorted in non-decreasing order.
bool arraySortedOrNot(int a[], int n)
{
// Base case
if (n == 1 || n == 0)
{
return true;
}
// Check if present index and index
// previous to it are in correct order
// and rest of the array is also sorted
// if true then return true else return
// false
return a[n - 1] >= a[n - 2] &&
arraySortedOrNot(a, n - 1);
}
// Driver code
int main()
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
if (arraySortedOrNot(arr, n))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}
// This code is contributed by avanitrachhadiya2155
Java
// Java Recursive approach to check if an
// Array is sorted or not
class GFG {
// Function that returns true if array is
// sorted in non-decreasing order.
static boolean arraySortedOrNot(int a[], int n)
{
// base case
if (n == 1 || n == 0)
return true;
// check if present index and index
// previous to it are in correct order
// and rest of the array is also sorted
// if true then return true else return
// false
return a[n - 1] >= a[n - 2]
&& arraySortedOrNot(a, n - 1);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = arr.length;
// Function Call
if (arraySortedOrNot(arr, n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Durgesh N. Birmiwal.
Python3
# Python3 recursive program to check
# if an Array is sorted or not
# Function that returns true if array
# is sorted in non-decreasing order.
def arraySortedOrNot(arr, n):
# Base case
if (n == 0 or n == 1):
return True
# Check if present index and index
# previous to it are in correct order
# and rest of the array is also sorted
# if true then return true else return
# false
return (arr[n - 1] >= arr[n - 2] and
arraySortedOrNot(arr, n - 1))
# Driver code
arr = [ 20, 23, 23, 45, 78, 88 ]
n = len(arr)
# Function Call
if (arraySortedOrNot(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by Virusbuddah
C#
// C# recursive approach to check if an
// Array is sorted or not
using System;
class GFG{
// Function that returns true if array is
// sorted in non-decreasing order.
static bool arraySortedOrNot(int[] a, int n)
{
// Base case
if (n == 1 || n == 0)
{
return true;
}
// Check if present index and index
// previous to it are in correct order
// and rest of the array is also sorted
// if true then return true else return
// false
return a[n - 1] >= a[n - 2] &&
arraySortedOrNot(a, n - 1);
}
// Driver code
static public void Main()
{
int[] arr = { 20, 23, 23, 45, 78, 88 };
int n = arr.Length;
// Function Call
if (arraySortedOrNot(arr, n))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by rag2127
Javascript
<script>
// JavaScript Recursive approach to check if an
// Array is sorted or not
// Function that returns true if array is
// sorted in non-decreasing order.
function arraySortedOrNot(a, n)
{
// Base case
if (n == 1 || n == 0)
{
return true;
}
// Check if present index and index
// previous to it are in correct order
// and rest of the array is also sorted
// if true then return true else return
// false
return a[n - 1] >= a[n - 2] &&
arraySortedOrNot(a, n - 1);
}
// Driver code
let arr = [ 20, 23, 23, 45, 78, 88 ];
let n = arr.length;
// Function Call
if (arraySortedOrNot(arr, n))
{
document.write("Yes" + "<br>");
}
else
{
document.write("No" + "<br>");
}
// This code is contributed by Surbhi Tyagi.
</script>
Producción
Yes
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n) para pila de llamadas recursivas.
Enfoque iterativo: la idea es más o menos la misma. El beneficio del enfoque iterativo es que evita el uso del espacio de la pila de recursividad y la sobrecarga de recursión.
A continuación se muestra la implementación mediante iteración:
C++
// C++ program to check if an
// Array is sorted or not
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if array is
// sorted in non-decreasing order.
bool arraySortedOrNot(int arr[], int n)
{
// Array has one or no element
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
// Unsorted pair found
if (arr[i - 1] > arr[i])
return false;
// No unsorted pair found
return true;
}
// Driver code
int main()
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = sizeof(arr) / sizeof(arr[0]);
if (arraySortedOrNot(arr, n))
cout << "Yes\n";
else
cout << "No\n";
}
Java
// Recursive approach to check if an
// Array is sorted or not
class GFG {
// Function that returns true if array is
// sorted in non-decreasing order.
static boolean arraySortedOrNot(int arr[], int n)
{
// Array has one or no element
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
// Unsorted pair found
if (arr[i - 1] > arr[i])
return false;
// No unsorted pair found
return true;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = arr.length;
if (arraySortedOrNot(arr, n))
System.out.print("Yes\n");
else
System.out.print("No\n");
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to check if an
# Array is sorted or not
# Function that returns true if array is
# sorted in non-decreasing order.
def arraySortedOrNot(arr, n):
# Array has one or no element
if (n == 0 or n == 1):
return True
for i in range(1, n):
# Unsorted pair found
if (arr[i-1] > arr[i]):
return False
# No unsorted pair found
return True
# Driver code
arr = [20, 23, 23, 45, 78, 88]
n = len(arr)
if (arraySortedOrNot(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by Anant Agarwal.
C#
// Recursive approach to check if an
// Array is sorted or not
using System;
class GFG
{
// Function that returns true if array is
// sorted in non-decreasing order.
static bool arraySortedOrNot(int []arr, int n)
{
// Array has one or no element
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
// Unsorted pair found
if (arr[i - 1] > arr[i])
return false;
// No unsorted pair found
return true;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 20, 23, 23, 45, 78, 88 };
int n = arr.Length;
if (arraySortedOrNot(arr, n))
Console.Write("Yes\n");
else
Console.Write("No\n");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program Recursive approach to check if an
// Array is sorted or not
// Function that returns true if array is
// sorted in non-decreasing order.
function arraySortedOrNot(arr, n)
{
// Array has one or no element
if (n == 0 || n == 1)
return true;
for (let i = 1; i < n; i++)
// Unsorted pair found
if (arr[i - 1] > arr[i])
return false;
// No unsorted pair found
return true;
}
// Driver Code
let arr = [ 20, 23, 23, 45, 78, 88 ];
let n = arr.length;
if (arraySortedOrNot(arr, n))
document.write("Yes\n");
else
document.write("No\n");
// This code is contributed by sanjoy_62.
</script>
Producción
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA