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)