Las arrays ordenadas circularmente son arrays que se ordenan en orden ascendente o descendente y luego se rotan en una serie de pasos.
Tomemos un ejemplo para saber más sobre arrays ordenadas circularmente:
Considere una array: arr[] = {23, 34, 45, 12, 17, 19}
Los elementos aquí, {12, 17, 19, 23, 34, 45} están ordenados ‘en orden’ pero rotados para la izquierda por 3 veces.
Array ordenada circularmente ascendente :
- Considere una array ordenada en orden ascendente: arr[] = {12, 17, 19, 23, 34, 45}
- Si la array anterior se gira 3 pasos hacia la izquierda, la array resultante será una array ordenada circularmente ascendente: {23, 34, 45, 12, 17, 19}
Array descendente ordenada circularmente:
- Considere una array ordenada en orden descendente: arr[] = {35, 26, 11, 9, 5, 3}
- Si la array anterior se gira 3 pasos hacia la izquierda, la array resultante será una array ordenada circularmente descendente: {9, 5, 3, 35, 26, 11}
Revisemos el siguiente problema si la array dada está ordenada circularmente o no:
Planteamiento del problema:
Dada una array arr[] de longitud N , la tarea es verificar si la array dada está ordenada circularmente o no, debemos verificar si la array dada es la forma rotada de la array ordenada.
- En una array ordenada circularmente ascendente, habrá como máximo un caso en el que el elemento justo antes del elemento actual será mayor que el elemento actual, es decir, arr[ i – 1 ] > arr[ i ] . Entonces, necesitamos contar la existencia total de tales casos y si el conteo es mayor que 1, el resultado será falso; de lo contrario, el resultado será verdadero, lo que significa que la array está ordenada circularmente .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check whether
// the array is circularly sorted
#include <bits/stdc++.h>
using namespace std;
// Function to check whether
// array is circularly sorted
bool checkCircularSorted(int arr[], int n)
{
// cnt variable will store count of
// arr[i-1] > arr[i]
int cnt = 0;
for (int i = 1; i < n; i++) {
// increase cnt if arr[i-1] > arr[i]
if (arr[i - 1] > arr[i]) {
cnt++;
}
}
// if cnt > 1 then false
// else true
if (cnt > 1) {
return false;
}
else {
return true;
}
}
// Driver code
int main()
{
// Given array
int arr[] = { 23, 34, 45, 12, 17, 19 };
// size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Calling function to check
// cirularly sorted array
bool result = checkCircularSorted(arr, N);
// Print result
if (result) {
cout << "Array is circularly sorted";
}
else {
cout << "Array is not circularly sorted";
}
}
Java
// Java program to check whether
// the array is circularly sorted
public class Main {
// Method to check whether
// array is circularly sorted
public static boolean checkCircularSorted(int arr[])
{
// cnt variable will store
// count of arr[i-1] > arr[i]
int cnt = 0;
for (int i = 1; i < arr.length; i++) {
// increase cnt if arr[i-1] > arr[i]
if (arr[i - 1] > arr[i]) {
cnt++;
}
}
// if cnt > 1 then false
// else true
if (cnt > 1) {
return false;
}
else {
return true;
}
}
// Driver code
public static void main(String args[])
{
// Given array
int arr[] = { 23, 34, 45, 12, 17, 19 };
// calling method to check
// cirularly sorted array
boolean result = checkCircularSorted(arr);
// print result
if (result == true) {
System.out.println(
"Array is circularly sorted");
}
else {
System.out.println(
"Array is not circularly sorted");
}
}
}
Python
# Python program to check whether
# the array is circularly sorted
# Function to check whether
# array is circularly sorted
def checkCircularSorted(arr) :
# cnt variable will store count of
# arr[i-1] > arr[i]
cnt = 0
n = len(arr)
for i in range(1,n) :
# increase cnt if arr[i-1] > arr[i]
if arr[i - 1] > arr[i] :
cnt+=1
# if cnt > 1 then false
# else true
if cnt > 1 :
return False
else :
return True
# Driver code
if __name__ == '__main__':
# Given array
arr = [ 23, 34, 45, 12, 17, 19 ]
# Calling function to check
# cirularly sorted array
result = checkCircularSorted(arr);
# Print result
if result == True :
print("Array is circularly sorted")
else :
print("Array is not circularly sorted")
# This code has been contributed by Sachin Sahara (sachin801)
C#
// C# program to check whether
// the array is circularly sorted
using System;
public class GFG {
// Method to check whether
// array is circularly sorted
public static bool checkCircularSorted(int []arr)
{
// cnt variable will store
// count of arr[i-1] > arr[i]
int cnt = 0;
for (int i = 1; i < arr.Length; i++) {
// increase cnt if arr[i-1] > arr[i]
if (arr[i - 1] > arr[i]) {
cnt++;
}
}
// if cnt > 1 then false
// else true
if (cnt > 1) {
return false;
}
else {
return true;
}
}
// Driver code
public static void Main(string []args)
{
// Given array
int []arr = { 23, 34, 45, 12, 17, 19 };
// calling method to check
// cirularly sorted array
bool result = checkCircularSorted(arr);
// print result
if (result == true) {
Console.WriteLine("Array is circularly sorted");
}
else {
Console.WriteLine("Array is not circularly sorted");
}
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program to check whether
// the array is circularly sorted
// Function to check whether
// array is circularly sorted
function checkCircularSorted(arr, n)
{
// cnt variable will store count of
// arr[i-1] > arr[i]
let cnt = 0;
for (let i = 1; i < n; i++) {
// increase cnt if arr[i-1] > arr[i]
if (arr[i - 1] > arr[i]) {
cnt++;
}
}
// if cnt > 1 then false
// else true
if (cnt > 1) {
return false;
}
else {
return true;
}
}
// Driver code
// Given array
let arr = [ 23, 34, 45, 12, 17, 19 ];
// size of array
let N = arr.length;
// Calling function to check
// cirularly sorted array
let result = checkCircularSorted(arr, N);
// Print result
if (result) {
document.write("Array is circularly sorted","</br>");
}
else {
document.write("Array is not circularly sorted","</br>");
}
// This code is contributed by shinjanpatra
</script>
Producción
Array is circularly sorted
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
De manera similar, podemos hacer la operación anterior para descender una array ordenada circularmente . En este caso, debemos considerar el recuento del caso donde, arr [i-1] < arr[i] .
Artículos relacionados: