Сортировать массив в указанном диапазоне индексов

Опубликовано: 5 Января, 2022

Дан массив arr [] из N целых чисел и диапазон индексов [a, b] . Задача состоит в том, чтобы отсортировать массив в этом заданном диапазоне индексов, т.е. отсортировать элементы массива от arr [a] до arr [b] , сохраняя при этом позиции других элементов, и распечатать измененный массив.
Примечание: Там нет никакой связи между а и Ь т.е. может быть меньше, равна или больше , чем Ь. Кроме того, 0 ≤ a, b <N

Примеры:

Input: arr[] = {7, 8, 4, 5, 2}, a = 1, b = 4
Output: 7 2 4 5 8
For the index range [1, 4] we get the elements 8, 4, 5 and 2
On sorting these elements we get 2, 4, 5 and 8.
So the array is modified as {7, 2, 4, 5, 8}
Input: arr[] = {20, 10, 3, 8}, a = 3, b = 1
Output: 20 3 8 10

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Создайте временный массив элементов для данного диапазона индексов массива.
Отсортируйте этот временный массив.
Теперь измените исходный массив этими отсортированными элементами временного массива для данного диапазона индексов.

Ниже представлена реализация описанного выше подхода:

C ++

 // 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);
    }
 }

Python3

 # 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 #

 // 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
 # 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
    ?>

Javascript

 <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

Ниже приведено прямое решение с использованием Arrays.sort ()

C ++

 // 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

 # 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 #

 // 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); 

                    
                                            Technical Scripter
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023