Рубрики

Программа для проверки, отсортирован массив или нет (итеративный и рекурсивный)

Учитывая массив размера n , напишите программу, чтобы проверить, отсортирована ли она в порядке возрастания или нет. В массиве допускаются равные значения, и два последовательных равных значения считаются отсортированными.

Примеры:

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

Рекурсивный подход:

Основная идея рекурсивного подхода:

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.

Ниже приведена реализация с использованием рекурсии:

C ++

// Рекурсивный подход для проверки, если
// Массив отсортирован или нет
#include <bits/stdc++.h>

using namespace std;

  
// Функция, которая возвращает 0, если пара
// найден несортированным

int arraySortedOrNot(int arr[], int n)

{

    // Массив имеет один или нет элемента или

    // остальные уже проверены и одобрены.

    if (n == 1 || n == 0)

        return 1;

  

    // Найдена несортированная пара (допустимы равные значения)

    if (arr[n - 1] < arr[n - 2])

        return 0;

  

    // Последняя пара была отсортирована

    // Продолжаем проверять

    return arraySortedOrNot(arr, n - 1);

}

  
// Код драйвера

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";

}

Джава

// Рекурсивный подход для проверки, если
// Массив отсортирован или нет

  

class CkeckSorted {

    // Функция, которая возвращает 0, если пара

    // найден несортированным

    static int arraySortedOrNot(int arr[], int n)

    {

        // Массив имеет один или нет элемента или

        // остальные уже проверены и одобрены.

        if (n == 1 || n == 0)

            return 1;

  

        // Найдена несортированная пара (допустимы равные значения)

        if (arr[n - 1] < arr[n - 2])

            return 0;

  

        // Последняя пара была отсортирована

        // Продолжаем проверять

        return arraySortedOrNot(arr, n - 1);

    }

  

    // основная функция

    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

# Рекурсивный подход для проверки, если
# Массив отсортирован или нет

  
# Функция, которая возвращает 0, если пара
# найдено несортированным

def arraySortedOrNot(arr):

      

    # Расчет длины

    n = len(arr)

      

    # Массив имеет один или нет элемента или

    # остальные уже проверены и одобрены.

    if n == 1 or n == 0:

        return True

          

    # Рекурсия применяется до последнего элемента

    return arr[0]<= arr[1] and arraySortedOrNot(arr[1:])

  

  

arr = [20, 23, 23, 45, 78, 88]

  
# Отображение результата

if arraySortedOrNot(arr): print("Yes")

else: print("No"

C #

// Рекурсивный подход для проверки, если
// Массив отсортирован или нет

using System;

      

class CkeckSorted

{

    // Функция, которая возвращает 0, если пара

    // найден несортированным

    static int arraySortedOrNot(int []arr, int n)

    {

        // Массив имеет один или нет элемента или

        // остальные уже проверены и одобрены.

        if (n == 1 || n == 0)

            return 1;

  

        // Найдена несортированная пара (допустимы равные значения)

        if (arr[n - 1] < arr[n - 2])

            return 0;

  

        // Последняя пара была отсортирована

        // Продолжаем проверять

        return arraySortedOrNot(arr, n - 1);

    }

  

    // Код драйвера

    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");

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

Yes

Сложность времени: O (n)
Вспомогательное пространство: O (n) для стека рекурсивных вызовов.

Итеративный подход: идея почти такая же. Преимущество итеративного подхода состоит в том, что он позволяет избежать использования пространства стека рекурсии и затрат на рекурсию.

Ниже приведена реализация с использованием итерации:

C ++

// C ++ программа для проверки, если
// Массив отсортирован или нет
#include <bits/stdc++.h>

using namespace std;

  
// Функция, которая возвращает true, если массив
// отсортировано в порядке убывания

bool arraySortedOrNot(int arr[], int n)

{

    // Массив имеет один или нет элемента

    if (n == 0 || n == 1)

        return true;

  

    for (int i = 1; i < n; i++)

  

        // Найдена несортированная пара

        if (arr[i - 1] > arr[i])

            return false;

  

    // Не найдена несортированная пара

    return true;

}

  
// Код драйвера

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";

}

Джава

// Рекурсивный подход для проверки, если
// Массив отсортирован или нет

class GFG {

  

    // Функция, которая возвращает true, если массив

    // отсортировано в порядке убывания

    static boolean arraySortedOrNot(int arr[], int n)

    {

  

        // Массив имеет один или нет элемента

        if (n == 0 || n == 1)

            return true;

  

        for (int i = 1; i < n; i++)

  

            // Найдена несортированная пара

            if (arr[i - 1] > arr[i])

                return false;

  

        // Не найдена несортированная пара

        return true;

    }

  

    // код драйвера

    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");

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для проверки, если
# Массив отсортирован или нет

  
# Функция, которая возвращает true, если массив
# отсортировано в порядке убывания.

def arraySortedOrNot(arr, n):

  

    # В массиве есть один элемент или его нет

    if (n == 0 or n == 1):

        return True

  

    for i in range(1, n):

  

        # Найдена несортированная пара

        if (arr[i-1] > arr[i]):

            return False

  

    # Не найдена несортированная пара

    return True

  

  
# Код драйвера

arr = [20, 23, 23, 45, 78, 88]

n = len(arr)

if (arraySortedOrNot(arr, n)):

    print("Yes")

else:

    print("No")

      
# Этот код предоставлен Anant Agarwal.

C #

// Рекурсивный подход для проверки, если
// Массив отсортирован или нет

using System;

  

class GFG

{

  

    // Функция, которая возвращает true, если массив

    // отсортировано в порядке убывания

    static bool arraySortedOrNot(int []arr, int n)

    {

  

        // Массив имеет один или нет элемента

        if (n == 0 || n == 1)

            return true;

  

        for (int i = 1; i < n; i++)

  

            // Найдена несортированная пара

            if (arr[i - 1] > arr[i])

                return false;

  

        // Не найдена несортированная пара

        return true;

    }

  

    // Код драйвера

    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");

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход:

Yes

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

Эта статья предоставлена Rohit Thapliyal . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Программа для проверки, отсортирован массив или нет (итеративный и рекурсивный)

0.00 (0%) 0 votes