Programa C++ para ordenar todos los elementos de la array excepto uno

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 .  

1. Intercambiar k-ésimo elemento con el último elemento.
2. Ordena todos los elementos excepto el último.
3. Para cada elemento desde (k+1)-ésimo hasta el último, muévalos una posición hacia adelante.1
4. Copie el k-ésimo elemento de vuelta a la posición k. 

// 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] << " ";
}

4 6 11 7 10 20 

Complejidad temporal : O(n*log(n)) donde n es el número de elementos.
Espacio Auxiliar : O(1)

¡ Consulte el artículo completo sobre Ordenar todos los elementos de la array excepto uno para obtener más detalles!