Ordenar la array en un rango de índice dado

Dada una array arr[] de N enteros y un rango de índice [a, b] . La tarea es ordenar la array en este rango de índice dado, es decir, ordenar los elementos de la array de arr[a] a arr[b] manteniendo intactas las posiciones de otros elementos e imprimir la array modificada. 
Nota: No existe una relación entre a y b , es decir, a puede ser menor, igual o mayor que b . Además, 0 ≤ a, b < N

Ejemplos: 

Entrada: arr[] = {7, 8, 4, 5, 2}, a = 1, b = 4 
Salida: 7 2 4 5 8 
Para el rango de índice [1, 4] obtenemos los elementos 8, 4, 5 y 2 
Al ordenar estos elementos obtenemos 2, 4, 5 y 8. 
Entonces la array se modifica como {7, 2, 4, 5, 8}

Entrada: arr[] = {20, 10, 3, 8}, a = 3, b = 1 
Salida: 20 3 8 10 

Acercarse: 

1. Cree una array temporal de los elementos para el rango de índice dado de la array.
2. Ordene esta array temporal.
3. Ahora modifique la array original con estos elementos ordenados de la array temporal para el rango de índice dado.

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

// C++ program to sort the
// array in a given index range
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the elements of the array
// from index a to index b
void partSort(int arr[], int N, int a, int b)
{
    // Variables to store start and
    // end of the index range
    int l = min(a, b);
    int r = max(a, b);
 
    // Temporary array
    int temp[r - l + 1];
    int j = 0;
    for (int i = l; i <= r; i++) {
        temp[j] = arr[i];
        j++;
    }
 
    // Sort the temporary array
    sort(temp, temp + r - l + 1);
 
    // Modifying original array with
    // temporary array elements
    j = 0;
    for (int i = l; i <= r; i++) {
            arr[i] = temp[j];
            j++;
    }
 
    // Print the modified array
    for (int i = 0; i < N; i++) {
            cout << arr[i] << " " ;
        }
         
}
 
 
// Driver code
int main()
{
    int arr[] = { 7, 8, 4, 5, 2 } ;
    int a = 1 ;
    int b = 4;
 
    // length of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    partSort(arr, N, a, b);
    return 0;
}
// This code is contributed by Ryuga

// Java program to sort the array in a given index range
import java.io.*;
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to sort the elements of the array
    // from index a to index b
    static void partSort(int[] arr, int N, int a, int b)
    {
        // Variables to store start and end of the index range
        int l = Math.min(a, b);
        int r = Math.max(a, b);
 
        // Temporary array
        int[] temp = new int[r - l + 1];
        int j = 0;
        for (int i = l; i <= r; i++) {
            temp[j] = arr[i];
            j++;
        }
 
        // Sort the temporary array
        Arrays.sort(temp);
 
        // Modifying original array with temporary array elements
        j = 0;
        for (int i = l; i <= r; i++) {
            arr[i] = temp[j];
            j++;
        }
 
        // Print the modified array
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int[] arr = { 7, 8, 4, 5, 2 };
        int a = 1, b = 4;
 
        // length of the array
        int N = arr.length;
 
        partSort(arr, N, a, b);
    }
}

# Python 3 program to sort the
# array in a given index range
 
# Function to sort the elements of
# the array from index a to index b
def partSort(arr, N, a, b):
     
    # Variables to store start and
    # end of the index range
    l = min(a, b)
    r = max(a, b)
 
    # Temporary array
    temp = [0 for i in range(r - l + 1)]
    j = 0
    for i in range(l, r + 1, 1):
        temp[j] = arr[i]
        j += 1
     
    # Sort the temporary array
    temp.sort(reverse = False)
 
    # Modifying original array with
    # temporary array elements
    j = 0
    for i in range(l, r + 1, 1):
            arr[i] = temp[j]
            j += 1
 
    # Print the modified array
    for i in range(0, N, 1):
            print(arr[i], end = " ")
 
# Driver code
if __name__ == '__main__':
    arr = [7, 8, 4, 5, 2]
    a = 1
    b = 4
 
    # length of the array
    N = len(arr)
 
    partSort(arr, N, a, b)
 
# This code is contributed by
# Surendra_Gangwar

// C# program to sort the array in a given index range
using System;
class GFG {
 
    // Function to sort the elements of the array
    // from index a to index b
    static void partSort(int[] arr, int N, int a, int b)
    {
        // Variables to store start and end of the index range
        int l = Math.Min(a, b);
        int r = Math.Max(a, b);
 
        // Temporary array
        int[] temp = new int[r - l + 1];
        int j = 0;
        for (int i = l; i <= r; i++) {
            temp[j] = arr[i];
            j++;
        }
 
        // Sort the temporary array
        Array.Sort(temp);
 
        // Modifying original array with temporary array elements
        j = 0;
        for (int i = l; i <= r; i++) {
            arr[i] = temp[j];
            j++;
        }
 
        // Print the modified array
        for (int i = 0; i < N; i++) {
            Console.Write(arr[i] + " ");
        }
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 7, 8, 4, 5, 2 };
        int a = 1, b = 4;
 
        // length of the array
        int N = arr.Length;
 
        partSort(arr, N, a, b);
    }
}
// This code is contributed by anuj_67

<?php
# PHP program to sort the
# array in a given index range
 
 
 
// Function to sort the elements of the array
// from index a to index b
function partSort( $arr, $N, $a, $b)
{
    // Variables to store start and
    // end of the index range
    $l = min($a, $b);
     $r = max($a, $b);
 
    // Temporary array
    $temp = array();
    $j = 0;
    for ($i = $l; $i <= $r; $i++) {
        $temp[$j] = $arr[$i];
        $j++;
    }
 
    // Sort the temporary array
    sort($temp);
 
    // Modifying original array with
    // temporary array elements
    $j = 0;
    for ($i = $l; $i <= $r; $i++) {
            $arr[$i] = $temp[$j];
            $j++;
    }
 
    // Print the modified array
    for ($i = 0; $i < $N; $i++) {
            echo $arr[$i]." " ;
        }
         
}
 
 
 
    $arr = array( 7, 8, 4, 5, 2 ) ;
    $a = 1 ;
    $b = 4;
 
    // length of the array
    $N = count($arr);
 
    partSort($arr, $N, $a, $b);
    //This code is contributed by 29AjayKumar
    ?>

<script>
    // Javascript program to sort the array in a given index range
     
    // Function to sort the elements of the array
    // from index a to index b
    function partSort(arr, N, a, b)
    {
        // Variables to store start and end of the index range
        let l = Math.min(a, b);
        let r = Math.max(a, b);
  
        // Temporary array
        let temp = new Array(r - l + 1);
        temp.fill(0);
        let j = 0;
        for (let i = l; i <= r; i++) {
            temp[j] = arr[i];
            j++;
        }
  
        // Sort the temporary array
        temp.sort(function(a, b){return a - b});
  
        // Modifying original array with temporary array elements
        j = 0;
        for (let i = l; i <= r; i++) {
            arr[i] = temp[j];
            j++;
        }
  
        // Print the modified array
        for (let i = 0; i < N; i++) {
            document.write(arr[i] + " ");
        }
    }
     
    let arr = [ 7, 8, 4, 5, 2 ];
    let a = 1, b = 4;
 
    // length of the array
    let N = arr.length;
 
    partSort(arr, N, a, b);
 
</script>

7 2 4 5 8

Complejidad de Tiempo: O(nlog(n))
Espacio Auxiliar: O(n)

A continuación se muestra una solución directa usando Arrays.sort() 

// C++ program to sort the array in a given index range
#include<bits/stdc++.h>
using namespace std;
 
    // Function to sort the elements of the array
    // from index a to index b
    void partSort(int arr[], int N, int a, int b)
    {
        // Variables to store start and end
        // of the index range
        int l = min(a, b);
        int r = max(a, b);
         
        vector<int> v(arr, arr + N);
 
        // Sort the subarray from arr[l] to
        // arr[r]
        sort(v.begin() + l, v.begin() + r + 1);
 
        // Print the modified array
        for (int i = 0; i < N; i++)
            cout << v[i] << " ";
    }
 
    // Driver code
    int main()
    {
        int arr[] = { 7, 8, 4, 5, 2 };
        int a = 1, b = 4;
        int N = sizeof(arr)/sizeof(arr[0]);
        partSort(arr, N, a, b);
    }
     
// This code is contributed by
// Sanjit_Prasad

// Java program to sort the array in a given index range
import java.io.*;
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to sort the elements of the array
    // from index a to index b
    static void partSort(int[] arr, int N, int a, int b)
    {
        // Variables to store start and end
        // of the index range
        int l = Math.min(a, b);
        int r = Math.max(a, b);
 
        // Sort the subarray from arr[l] to
        // arr[r]
        Arrays.sort(arr, l, r + 1);
 
        // Print the modified array
        for (int i = 0; i < N; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver code
    public static void main(String args[])
    {
        int[] arr = { 7, 8, 4, 5, 2 };
        int a = 1, b = 4;
        int N = arr.length;
        partSort(arr, N, a, b);
    }
}

# Python3 program to sort the
# array in a given index range
 
# Function to sort the elements of
# the array from index a to index b
def partSort(arr, N, a, b):
     
    # Variables to store start and
    # end of the index range
    l = min(a, b)
    r = max(a, b)
 
    arr = (arr[0 : l] +
    sorted(arr[l : r + 1]) +
           arr[r : N])
 
    # Print the modified array
    for i in range(0, N, 1):
            print(arr[i], end = " ")
 
# Driver code
if __name__ == '__main__':
     
    arr = [ 7, 8, 4, 5, 2 ]
    a = 1
    b = 4
 
    # Length of the array
    N = len(arr)
 
    partSort(arr, N, a, b)
 
# This code is contributed by grand_master

// C# program to sort the array in a given index range
using System;
 
class GFG {
 
    // Function to sort the elements of the array
    // from index a to index b
    static void partSort(int[] arr, int N, int a, int b)
    {
        // Variables to store start and end
        // of the index range
        int l = Math.Min(a, b);
        int r = Math.Max(a, b);
 
        // Sort the subarray from arr[l] to
        // arr[r]
        Array.Sort(arr, l, r);
 
        // Print the modified array
        for (int i = 0; i < N; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver code
    static void Main()
    {
        int[] arr = { 7, 8, 4, 5, 2 };
        int a = 1, b = 4;
        int N = arr.Length;
        partSort(arr, N, a, b);
    }
}
 
// This code is contributed by mits

<script>
// javascript program to sort the array in a given index range
// Function to sort the elements of the array
// from index a to index b
function swap(arr, xp, yp)
{
    var temp = arr[xp];
    arr[xp] = arr[yp];
    arr[yp] = temp;
}
    function partSort(arr , N , a , b)
    {
     
        // Variables to store start and end
        // of the index range
        var l = Math.min(a, b);
        var r = Math.max(a, b);
 
        // Sort the subarray from arr[l] to
        // arr[r]
        //.sort(arr, l, r + 1);
        var i, j;
        for (i = l; i < r + 1 + 1; i++)
        {
            for (j = l; j < r - i + 1; j++)
            {
        if (arr[j] > arr[j + 1])
        {
        swap(arr, j, j + 1);
           
        }
    }
   
}
 
        // Print the modified array
        for (i = 0; i < N; i++)
            document.write(arr[i] + " ");
    }
 
    // Driver code
        var arr = [ 7, 8, 4, 5, 2 ];
        var a = 1, b = 4;
        var N = arr.length;
        partSort(arr, N, a, b);
 
// This code is contributed by gauravrajput1
</script>

7 2 4 5 8

Complejidad de Tiempo: O(nlog(n))
Espacio Auxiliar: O(n)