Dada una array, un entero positivo, ordene la array en orden ascendente de modo que el elemento en el índice K en la array no ordenada permanezca inmóvil y todos los demás elementos estén ordenados.
Ejemplos:
Input : arr[] = {10, 4, 11, 7, 6, 20}
k = 2;
Output : arr[] = {4, 6, 11, 7, 10, 20}
Input : arr[] = {30, 20, 10}
k = 0
Output : arr[] = {30, 10, 20}
Una solución simple es copiar todos los elementos excepto el k-ésimo de una array dada a otra array. Luego ordene la otra array usando un algoritmo de clasificación. Finalmente, copie nuevamente la array ordenada en la array original. Mientras copia, salte el k-ésimo elemento.
A continuación se muestra una solución eficiente .
- Intercambiar k-ésimo elemento con el último elemento.
- Ordena todos los elementos excepto el último.
- Para cada elemento desde (k+1)-ésimo hasta el último, muévalos una posición hacia adelante.1
- Copie el k-ésimo elemento de vuelta a la posición k.
C++
// CPP program to sort all elements except
// element at index k.
#include <bits/stdc++.h>
using namespace std;
int sortExceptK(int arr[], int k, int n)
{
// Move k-th element to end
swap(arr[k], arr[n-1]);
// Sort all elements except last
sort(arr, arr + n - 1);
// Store last element (originally k-th)
int last = arr[n-1];
// Move all elements from k-th to one
// position ahead.
for (int i=n-1; i>k; i--)
arr[i] = arr[i-1];
// Restore k-th element
arr[k] = last;
}
// Driver code
int main()
{
int a[] = {10, 4, 11, 7, 6, 20 };
int k = 2;
int n = sizeof(a) / sizeof(a[0]);
sortExceptK(a, k, n);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
Java
// Java program to sort all elements except
// element at index k.
import java.util.Arrays;
class GFG {
static int sortExceptK(int arr[], int k, int n)
{
// Move k-th element to end
int temp = arr[k];
arr[k] = arr[n-1];
arr[n-1] = temp;
// Sort all elements except last
Arrays.sort(arr, 0, n-1);
// Store last element (originally k-th)
int last = arr[n-1];
// Move all elements from k-th to one
// position ahead.
for (int i = n-1; i > k; i--)
arr[i] = arr[i-1];
// Restore k-th element
arr[k] = last;
return 0;
}
//Driver code
public static void main (String[] args)
{
int a[] = {10, 4, 11, 7, 6, 20 };
int k = 2;
int n = a.length;
sortExceptK(a, k, n);
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
}
//This code is contributed by Anant Agarwal.
Python3
# Python3 program to sort all elements except
# element at index k.
def sortExcept(arr, k, n):
# Move k-th element to end
arr[k], arr[-1] = arr[-1], arr[k]
# Sort all elements except last
arr = sorted(arr, key = lambda i: (i is arr[-1], i))
# Store last element (originally k-th)
last = arr[-1]
# Move all elements from k-th to one
# position ahead.
i = n - 1
while i > k:
arr[i] = arr[i - 1]
i -= 1
# Restore k-th element
arr[k] = last
return arr
# Driver code
if __name__ == '__main__':
a = [10, 4, 11, 7, 6, 20]
k = 2
n = len(a)
a = sortExcept(a, k, n)
print(" ".join(list(map(str, a))))
# This code is contributed by Shivam Singh.
C#
// C# program to sort all elements except
// element at index k.
using System;
public class GFG {
static int sortExceptK(int[] arr, int k, int n)
{
// Move k-th element to end
int temp = arr[k];
arr[k] = arr[n - 1];
arr[n - 1] = temp;
// Sort all elements except last
Array.Sort(arr, 0, n - 1);
// Store last element (originally k-th)
int last = arr[n - 1];
// Move all elements from k-th to one
// position ahead.
for (int i = n - 1; i > k; i--)
arr[i] = arr[i - 1];
// Restore k-th element
arr[k] = last;
return 0;
}
// Driver code
public static void Main()
{
int[] a = { 10, 4, 11, 7, 6, 20 };
int k = 2;
int n = a.Length;
sortExceptK(a, k, n);
for (int i = 0; i < n; i++)
Console.Write(a[i] + " ");
}
}
// This article is contributed by shiv_bhakt
PHP
<?php
// PHP program to sort all
// elements except element
// at index k.
function sortExceptK(&$arr, $k, $n)
{
// Move k-th element to end
$t = $arr[$k];
$arr[$k] = $arr[$n - 1];
$arr[$n - 1] = $t;
// Sort all elements
// except last
$t = $arr[count($arr) - 1];
$arr = array_slice($arr, 0, -1);
sort($arr);
array_push($arr, $t);
// Store last element
// (originally k-th)
$last = $arr[$n - 1];
// Move all elements from
// k-th to one position ahead.
for ($i = $n - 1; $i > $k; $i--)
$arr[$i] = $arr[$i - 1];
// Restore k-th element
$arr[$k] = $last;
}
// Driver code
$a = array(10, 4, 11,
7, 6, 20 );
$k = 2;
$n = count($a);
sortExceptK($a, $k, $n);
for ($i = 0; $i < $n; $i++)
echo ($a[$i]." ");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to sort all elements except
// element at index k.
function sortExceptK(arr, k, n)
{
// Move k-th element to end
let temp = arr[k];
arr[k] = arr[n-1];
arr[n-1] = temp;
// Sort all elements except last
arr.sort(function(a, b){
return a - b});
// Store last element (originally k-th)
let last = arr[n-1];
// Move all elements from k-th to one
// position ahead.
for (let i = n-1; i > k; i--)
arr[i] = arr[i-1];
// Restore k-th element
arr[k] = last;
// Move k-th element to end
temp = arr[k];
arr[k] = arr[n-1];
arr[n-1] = temp;
return 0;
}
let a = [10, 4, 11, 7, 6, 20 ];
let k = 2;
let n = a.length;
sortExceptK(a, k, n);
for(let i = 0; i < n; i++)
document.write(a[i] + " ");
</script>
Producción:
4 6 11 7 10 20
Complejidad temporal : O(n*log(n)) donde n es el número de elementos.
Espacio Auxiliar : O(1)