Ordene una array que contenga valores de 1 a N en O (N) usando Cycle Sort

Requisito previo: ordenación cíclica
Dada una array arr[] de elementos de 1 a N , la tarea es ordenar la array dada en tiempo O(N) .
Ejemplos:  

Entrada: arr[] = { 2, 1, 5, 4, 3} 
Salida: 1 2 3 4 5 
Explicación: 
Como arr[0] = 2 no está en la posición correcta, cambie arr[0] por arr[arr[ 0] – 1] 
Ahora la array se convierte en: arr[] = {1, 2, 5, 4, 3}
Ahora arr[2] = 5 no está en la posición correcta, luego intercambie arr[2] con arr[arr[2] – 1] 
Ahora la array se convierte en: arr[] = {1, 2, 3, 4, 5} 
Ahora la array está ordenada.
Entrada: arr[] = {1, 2, 3, 4, 5, 6} 
Salida: 1 2 3 4 5 6 
Explicación: 
La array ya está ordenada. 
 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . A continuación se muestran los pasos:  

  • Recorre la array dada arr[] .
  • Si el elemento actual no está en la posición correcta, es decir, arr[i] no es igual a i+1 , entonces, intercambie el elemento actual con el elemento con su posición correcta. 
    Por ejemplo: 
     

Sea arr[] = {2, 1, 4, 5, 3} 
Dado que, arr[0] = 2, que no está en su posición correcta 1. 
Luego intercambie este elemento con su posición correcta, es decir, swap(arr[0 ], arr[2-1]) 
Entonces la array se convierte en: arr[] = {1, 2, 4, 5, 3} 
 

  • Si el elemento actual está en la posición correcta, busque el siguiente elemento.
  • Repita los pasos anteriores hasta llegar al final de la array.

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program for the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to swap two a & b value
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
// Function to print array element
void printArray(int arr[], int N)
{
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        cout << arr[i] << ' ';
    }
}
 
// Function to sort the array in O(N)
void sortArray(int arr[], int N)
{
 
    // Traverse the array
    for (int i = 0; i < N;) {
 
        // If the current element is
        // at correct position
        if (arr[i] == i + 1) {
            i++;
        }
 
        // Else swap the current element
        // with it's correct position
        else {
            swap(&arr[i], &arr[arr[i] - 1]);
        }
    }
}
 
// Driver Code
int main()
{
 
    int arr[] = { 2, 1, 5, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to sort the array
    sortArray(arr, N);
 
    // Function call to print the array
    printArray(arr, N);
    return 0;
}

Java

// Java program for the above approach
class Main{
     
// Function to print array element
public static void printArray(int arr[], int N)
{
     
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
       System.out.print(arr[i] + " ");
    }
}
     
// Function to sort the array in O(N)
public static void sortArray(int arr[], int N)
{
 
    // Traverse the array
    for(int i = 0; i < N;)
    {
 
       // If the current element is
       // at correct position
       if (arr[i] == i + 1)
       {
           i++;
       }
        
       // Else swap the current element
       // with it's correct position
       else
       {
           // Swap the value of
           // arr[i] and arr[arr[i]-1]
           int temp1 = arr[i];
           int temp2 = arr[arr[i] - 1];
           arr[i] = temp2;
           arr[temp1 - 1] = temp1;
       }
    }
}
 
// Driver Code   
public static void main(String[] args)
{
    int arr[] = { 2, 1, 5, 3, 4 };
    int N = arr.length;
 
    // Function call to sort the array
    sortArray(arr, N);
 
    // Function call to print the array
    printArray(arr, N);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program for the above approach
 
# Function to print array element
def printArray(arr, N):
     
    # Traverse the array
    for i in range(N):
        print(arr[i], end = ' ')
         
# Function to sort the array in O(N)
def sortArray(arr, N):
     
    i = 0
     
    # Traverse the array
    while i < N:
         
        # If the current element is
        # at correct position
        if arr[i] == i + 1:
            i += 1
         
        # Else swap the current element
        # with it's correct position
        else:
             
            # Swap the value of
            # arr[i] and arr[arr[i]-1]
            temp1 = arr[i]
            temp2 = arr[arr[i] - 1]
            arr[i] = temp2
            arr[temp1 - 1] = temp1
     
# Driver code
if __name__=='__main__':
     
    arr = [ 2, 1, 5, 3, 4 ]
    N = len(arr)
     
    # Function call to sort the array
    sortArray(arr, N)
     
    # Function call to print the array
    printArray(arr, N)
 
# This code is contributed by rutvik_56   

C#

// C# program for the above approach
using System;
class GFG{
     
// Function to print array element
public static void printArray(int []arr, int N)
{   
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
       Console.Write(arr[i] + " ");
    }
}
     
// Function to sort the array in O(N)
public static void sortArray(int []arr, int N)
{
    // Traverse the array
    for(int i = 0; i < N; )
    {
       // If the current element is
       // at correct position
       if (arr[i] == i + 1)
       {
           i++;
       }
        
       // Else swap the current element
       // with it's correct position
       else
       {
           // Swap the value of
           // arr[i] and arr[arr[i]-1]
           int temp1 = arr[i];
           int temp2 = arr[arr[i] - 1];
           arr[i] = temp2;
           arr[temp1 - 1] = temp1;
       }
    }
}
 
// Driver Code   
public static void Main(String[] args)
{
    int []arr = {2, 1, 5, 3, 4};
    int N = arr.Length;
 
    // Function call to sort the array
    sortArray(arr, N);
 
    // Function call to print the array
    printArray(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to print array element
function printArray(arr, N)
{
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
        document.write( arr[i] + ' ');
    }
}
 
// Function to sort the array in O(N)
function sortArray(arr, N)
{
 
    // Traverse the array
    for (var i = 0; i < N;) {
 
        // If the current element is
        // at correct position
        if (arr[i] == i + 1) {
            i++;
        }
 
        // Else swap the current element
        // with it's correct position
        else {
            var temp1 = arr[i];
           var temp2 = arr[arr[i] - 1];
           arr[i] = temp2;
           arr[temp1 - 1] = temp1;
        }
    }
}
 
// Driver Code
var arr =  [ 2, 1, 5, 3, 4 ];
var N = arr.length;
 
// Function call to sort the array
sortArray(arr, N);
 
// Function call to print the array
printArray(arr, N);
 
// This code is contributed by noob2000.
</script>
Producción: 

1 2 3 4 5

 

Complejidad de tiempo: O(N) , donde N es la longitud de la array. 
Espacio Auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por coder001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *