Dada una array casi ordenada donde solo se intercambian dos elementos, ¿cómo ordenar la array de manera eficiente?
Ejemplos:
Input: arr[] = {10, 20, 60, 40, 50, 30}
// 30 and 60 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}
Input: arr[] = {10, 20, 40, 30, 50, 60}
// 30 and 40 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}
Input: arr[] = {1, 5, 3}
// 3 and 5 are swapped
Output: arr[] = {1, 3, 5}
La complejidad de tiempo esperada es O (n) y solo una operación de intercambio para arreglar la array.
La idea es atravesar desde el lado derecho y encontrar el primer elemento fuera de servicio (elemento que es más pequeño que el elemento anterior). Una vez que se encuentra el primer elemento, busque el otro elemento fuera de servicio recorriendo la array hacia el lado izquierdo.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to sort using one swap
#include<iostream>
#include<algorithm>
using namespace std;
// This function sorts an array that can be sorted
// by single swap
void sortByOneSwap(int arr[], int n)
{
// Traverse the given array from rightmost side
for (int i = n-1; i > 0; i--)
{
// Check if arr[i] is not in order
if (arr[i] < arr[i-1])
{
// Find the other element to be
// swapped with arr[i]
int j = i-1;
while (j>=0 && arr[i] < arr[j])
j--;
// Swap the pair
swap(arr[i], arr[j+1]);
break;
}
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = {10, 30, 20, 40, 50, 60, 70};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, n);
sortByOneSwap(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
return 0;
}
Java
// Java program to
// sort using one swap
import java.io.*;
class GFG
{
// This function sorts an array
// that can be sorted by single swap
static void sortByOneSwap(int arr[],
int n)
{
// Traverse the given array
// from rightmost side
for (int i = n - 1; i > 0; i--)
{
// Check if arr[i]
// is not in order
if (arr[i] < arr[i - 1])
{
// Find the other element
// to be swapped with arr[i]
int j = i - 1;
while (j >= 0 && arr[i] < arr[j])
j--;
// Swap the pair
int temp = arr[i];
arr[i] = arr[j + 1];
arr[j + 1] = temp;
break;
}
}
}
// A utility function to
// print an array of size n
static void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {10, 30, 20,
40, 50, 60, 70};
int n = arr.length;
System.out.println("Given array is ");
printArray(arr, n);
sortByOneSwap(arr, n);
System.out.println("Sorted array is ");
printArray(arr, n);
}
}
// This code is contributed by anuj_67.
Python3
# Python program to
# sort using one swap
# This function sorts an array
# that can be sorted by single swap
def sortByOneSwap(arr, n):
# Traverse the given array
# from rightmost side
for i in range(n - 1, 0, -1):
# Check if arr[i]
# is not in order
if (arr[i] < arr[i - 1]):
# Find the other element
# to be swapped with arr[i]
j = i - 1;
while (j >= 0 and arr[i] < arr[j]):
j -= 1;
# Swap the pair
temp = arr[i];
arr[i] = arr[j + 1];
arr[j + 1] = temp;
break;
# A utility function to
# print an array of size n
def printArray(arr, n):
for i in range(n):
print(arr[i], end = " ");
print();
# Driver Code
if __name__ == '__main__':
arr = [ 10, 30, 20, 40, 50, 60, 70 ];
n = len(arr);
print("Given array is ");
printArray(arr, n);
sortByOneSwap(arr, n);
print("Sorted array is ");
printArray(arr, n);
# This code is contributed by gauravrajput1
C#
// C# program to sort using one swap
using System;
class GFG
{
// This function sorts an array
// that can be sorted by single swap
static void sortByOneSwap(int []arr,
int n)
{
// Traverse the given array
// from rightmost side
for (int i = n - 1; i > 0; i--)
{
// Check if arr[i] is not in order
if (arr[i] < arr[i - 1])
{
// Find the other element to be
// swapped with arr[i]
int j = i - 1;
while (j >= 0 && arr[i] < arr[j])
j--;
// Swap the pair
int temp = arr[i];
arr[i] = arr[j + 1];
arr[j + 1] = temp;
break;
}
}
}
// A utility function to print an
// array of size n
static void printArray(int []arr, int n)
{
int i;
for (i = 0; i < n; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver Code
public static void Main()
{
int []arr = {10, 30, 20,
40, 50, 60, 70};
int n = arr.Length;
Console.WriteLine("Given array is ");
printArray(arr, n);
sortByOneSwap(arr, n);
Console.WriteLine("Sorted array is ");
printArray(arr, n);
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to sort using one swap
// This function sorts an array
// that can be sorted by single swap
function sortByOneSwap(&$arr, $n)
{
// Traverse the given array
// from rightmost side
for ($i = $n - 1; $i > 0; $i--)
{
// Check if arr[i]
// is not in order
if ($arr[$i] < $arr[$i - 1])
{
// Find the other element
// to be swapped with arr[i]
$j = $i - 1;
while ($j >= 0 && $arr[$i] < $arr[$j])
$j--;
// Swap the pair
$temp = $arr[$i];
$arr[$i] = $arr[$j + 1];
$arr[$j + 1] = $temp;
break;
}
}
}
// A utility function to
// print an array of size n
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
echo "\n";
}
// Driver Code
$arr = array(10, 30, 20,
40, 50, 60, 70);
$n = sizeof($arr);
echo "Given array is " . "\n";
printArray($arr, $n);
sortByOneSwap($arr, $n);
echo "Sorted array is ". "\n";
printArray($arr, $n);
// This code is contributed by Akanksha Rai
Javascript
<script>
// Javascript program to sort using one swap
// This function sorts an array
// that can be sorted by single swap
function sortByOneSwap(arr, n)
{
// Traverse the given array
// from rightmost side
for (let i = n - 1; i > 0; i--)
{
// Check if arr[i] is not in order
if (arr[i] < arr[i - 1])
{
// Find the other element to be
// swapped with arr[i]
let j = i - 1;
while (j >= 0 && arr[i] < arr[j])
j--;
// Swap the pair
let temp = arr[i];
arr[i] = arr[j + 1];
arr[j + 1] = temp;
break;
}
}
}
// A utility function to print an
// array of size n
function printArray(arr, n)
{
let i;
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
document.write("</br>");
}
let arr = [10, 30, 20, 40, 50, 60, 70];
let n = arr.length;
document.write("Given array is " + "</br>");
printArray(arr, n);
sortByOneSwap(arr, n);
document.write("Sorted array is " + "</br>");
printArray(arr, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción :
Given array is 10 30 20 40 50 60 70 Sorted array is 10 20 30 40 50 60 70
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar la array.
Espacio auxiliar : O(1), ya que no estamos usando espacio extra.
El programa anterior funciona en tiempo O(n) e intercambia solo un elemento.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA