Compruebe si la array dada está casi ordenada (los elementos están como máximo a una posición de distancia)

Dada una array con n elementos distintos. Se dice que una array está casi ordenada (no decreciente) si cualquiera de sus elementos puede aparecer a una distancia máxima de 1 de sus lugares originales en la array ordenada. Necesitamos encontrar si la array dada está casi ordenada o no.
Ejemplos: 
 

Input : arr[] = {1, 3, 2, 4}
Output : Yes
Explanation : All elements are either
at original place or at most a unit away. 

Input : arr[] = {1, 4, 2, 3}
Output : No
Explanation : 4 is 2 unit away from
its original place.

Enfoque de clasificación: con la ayuda de la clasificación, podemos predecir si nuestra array dada está casi ordenada o no. La idea detrás de eso es primero ordenar la array de entrada, digamos A [] y luego, si la array se ordenará casi, cada elemento Ai de la array dada debe ser igual a cualquiera de Bi-1, Bi o Bi + 1 de la array ordenada B [ ]. 
Complejidad de tiempo: O (nlogn) 
 

// suppose B[] is copy of A[]
sort(B, B+n);

// check first element
if ((A[0]!=B[0]) && (A[0]!=B[1]) )
    return 0;
// iterate over array
for(int i=1; i<n-1; i++)
{
    if (A[i]!=B[i-1]) && (A[i]!=B[i]) && (A[i]!=B[i+1]) )
        return false;
}
// check for last element
if ((A[i]!=B[i-1]) && (A[i]!=B[i]) )
    return 0;

// finally return true
return true;

Complejidad de tiempo: O(n Log n)
Enfoque eficiente: La idea se basa en Bubble Sort . Al igual que Bubble Sort, comparamos elementos adyacentes y los intercambiamos si no están en orden. Aquí, después del intercambio, movemos el índice una posición más para que el burbujeo se limite a un lugar. Entonces, después de una iteración, si la array resultante está ordenada, podemos decir que nuestra array de entrada estaba casi ordenada; de lo contrario, no estaba casi ordenada.
 

// perform bubble sort tech once
for (int i=0; i<n-1; i++)
    if (A[i+1]<A[i])
        swap(A[i], A[i+1]);
        i++;

// check whether resultant is sorted or not
for (int i=0; i<n-1; i++)
    if (A[i+1]<A[i])
        return false;

// If resultant is sorted return true
return true;

// CPP program to find whether given array
// almost sorted or not
#include <bits/stdc++.h>
using namespace std;
 
// function for checking almost sort
bool almostSort(int A[], int n)
{
    // One by one compare adjacents.
    for (int i = 0; i < n - 1; i++) {
        if (A[i] > A[i + 1]) {
            swap(A[i], A[i + 1]);
            i++;
        }
    }
 
    // check whether resultant is sorted or not
    for (int i = 0; i < n - 1; i++)
        if (A[i] > A[i + 1])
            return false;
 
    // is resultant is sorted return true
    return true;
}
 
// driver function
int main()
{
    int A[] = { 1, 3, 2, 4, 6, 5 };
    int n = sizeof(A) / sizeof(A[0]);
    if (almostSort(A, n))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

// JAVA Code to check if given array is almost
// sorted or not
import java.util.*;
 
class GFG {
     
    // function for checking almost sort
    public static boolean almostSort(int A[], int n)
    {
        // One by one compare adjacents.
        for (int i = 0; i < n - 1; i++) {
            if (A[i] > A[i + 1]) {
                int temp = A[i];
                A[i] = A[i+1];
                A[i+1] = temp;
                i++;
            }
        }
      
        // check whether resultant is sorted or not
        for (int i = 0; i < n - 1; i++)
            if (A[i] > A[i + 1])
                return false;
      
        // is resultant is sorted return true
        return true;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int A[] = { 1, 3, 2, 4, 6, 5 };
        int n = A.length;
        if (almostSort(A, n))
            System.out.print("Yes");
        else
            System.out.print("No");
         
    }
}
   
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to find whether given
# array almost sorted or not
 
# Function for checking almost sort
def almostSort(A, n):
 
    # One by one compare adjacents.
    i = 0
    while i < n - 1:
        if A[i] > A[i + 1]:
            A[i], A[i + 1] = A[i + 1], A[i]
            i += 1
         
        i += 1
 
    # check whether resultant is sorted or not
    for i in range(0, n - 1):
        if A[i] > A[i + 1]:
            return False
 
    # Is resultant is sorted return true
    return True
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 3, 2, 4, 6, 5]
    n = len(A)
    if almostSort(A, n):
        print("Yes")
    else:
        print("No")
     
# This code is contributed
# by Rituraj Jain

// C# Code to check if given array
// is almost sorted or not
using System;
 
class GFG {
     
    // function for checking almost sort
    public static bool almostSort(int []A, int n)
    {
         
        // One by one compare adjacents.
        for (int i = 0; i < n - 1; i++)
        {
            if (A[i] > A[i + 1])
            {
                int temp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = temp;
                i++;
            }
        }
     
        // Check whether resultant is
        // sorted or not
        for (int i = 0; i < n - 1; i++)
            if (A[i] > A[i + 1])
                return false;
     
        // is resultant is sorted return true
        return true;
    }
     
    // Driver Code
    public static void Main()
    {
        int []A = {1, 3, 2, 4, 6, 5};
        int n = A.Length;
        if (almostSort(A, n))
            Console.Write("Yes");
        else
            Console.Write("No");
         
    }
}
     
// This code is contributed by Nitin Mittal.

<?php
// PHP program to find
// whether given array
// almost sorted or not
 
// function for checking
// almost sort
function almostSort($A, $n)
{
    // One by one compare adjacents.
    for ($i = 0; $i < $n - 1; $i++)
    {
        if ($A[$i] > $A[$i + 1])
        {
            list($A[$i],
                 $A[$i + 1]) = array($A[$i + 1],
                                     $A[$i] );
             
            $i++;
        }
    }
 
    // check whether resultant
    // is sorted or not
    for ($i = 0; $i <$n - 1; $i++)
        if ($A[$i] > $A[$i + 1])
            return false;
 
    // is resultant is
    // sorted return true
    return true;
}
 
// Driver Code
$A = array (1, 3, 2,
            4, 6, 5);
$n = sizeof($A) ;
if (almostSort($A, $n))
    echo "Yes", "\n";
else
    echo "Yes", "\n";
     
 
// This code is contributed by ajit
?>

<script>
    // Javascript Code to check if given array
    // is almost sorted or not
     
    // function for checking almost sort
    function almostSort(A, n)
    {
           
        // One by one compare adjacents.
        for (let i = 0; i < n - 1; i++)
        {
            if (A[i] > A[i + 1])
            {
                let temp = A[i];
                A[i] = A[i + 1];
                A[i + 1] = temp;
                i++;
            }
        }
       
        // Check whether resultant is
        // sorted or not
        for (let i = 0; i < n - 1; i++)
            if (A[i] > A[i + 1])
                return false;
       
        // is resultant is sorted return true
        return true;
    }
     
    let A = [1, 3, 2, 4, 6, 5];
    let n = A.length;
    if (almostSort(A, n))
      document.write("Yes");
    else
      document.write("No");
     
</script>

Producción: 
 

Yes

Complejidad de tiempo : O (N), ya que estamos usando cualquier bucle para atravesar.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.