Рубрики

Разрешается сортировка массива с заменой только по специальному элементу

Для данного массива длиной n + 1, содержащего элементы с 1 по n и пробел, требуется использовать данную функцию подкачки (индекс i, индекс j) для сортировки массива. Вы можете поменять местами только пробел и число в конец, положить разрыв в конце.
Там будет число 999 в массиве как пробел или пробел.
Примеры:

Input  : arr = {1, 5, 4, 999, 3, 2}
Output : arr = {1, 2, 3, 4, 5, 999}
We need to sort only by moving 

Input  : arr = {1, 5, 4, 3, 2, 8, 7, 999, 6}
Output : arr = {1, 2, 3, 4, 5, 6, 7, 8, 999}

Мы используем рекурсивный подход для решения этой проблемы. Как мы можем поменять местами только цифры с пробелом. Прежде всего мы найдем указатель пространства. Если индекс является началом массива, то переместите это пространство на второй последний индекс, поменяв местами каждое число справа.
Если пробел не является ни началом массива, ни последним элементом массива, ни элементом перед ним больше, чем элемент рядом с пробелом, выполните следующее.

Step 1: Swap space and element next to space
In case of {3, 999, 2} make it {3, 2, 999}

Step 2 : Swap space and greater element
eg-convert {3, 2, 999} to {999, 2, 3}

В противном случае элементы рядом с индексом сортируются и меняются местами с предыдущим элементом. Снова вызовите функцию сортировки с уменьшенным размером массива на 1 и индексом пробела — 1, так как каждый раз мы получим один отсортированный элемент.

C ++

// Программа CPP для сортировки массива путем перемещения
// пространство вокруг.
#include <bits/stdc++.h>

using namespace std;

  
// n - общее количество элементов.
// индекс - это индекс 999 или пробел.
// k - количество элементов, которые еще предстоит отсортировать.

void sortRec(int arr[], int index, int k, int n)

{

    // выводим отсортированный массив при достижении цикла

    // базовый случай

    if (k == 0) {

        for (int i = 1; i < n; i++)

            cout << arr[i] << " ";

        cout << 999;

        return;

    }

  

    // иначе, если k> 0 и пробел находится в 0-м индексе

    // каждый номер с пробелом и сохранением индекса в

    // второй последний индекс

    else if (k > 0 && index == 0) {

        index = n - 2;

        for (int i = 1; i <= index; i++) {

            arr[i - 1] = arr[i];

        }

        arr[index] = 999;

    }

  

    // если пробел не является ни началом массива, ни последним

    // элемент массива и элемент перед ним больше

    // чем / элемент рядом с пробелом

    if (index - 1 >= 0 && index + 1 < n && 

       arr[index - 1] > arr[index + 1]) {

  

        // первый обмен пространства и элемент рядом с пробелом

        // в случае {3, 999, 2} сделать это {3, 2, 999}

        swap(arr[index], arr[index + 1]);

  

        // чем пространство подкачки и больший элемент

        // преобразовать {3, 2, 999} в {999, 2, 3}

        swap(arr[index - 1], arr[index + 1]);

    }

  

    else

        swap(arr[index], arr[index - 1]);

  

    sortRec(arr, index - 1, k - 1, n);

}

  
// Обёртка над sortRec.

void sort(int arr[], int n)

{

    // Найти индекс пробела (или 999)

    int index = -1;

    for (int i = 0; i < n; i++) {

        if (arr[i] == 999) {

            index = i;

            break;

        }

    }

  

    // Неверный Ввод

    if (index == -1)

        return;

  

    sortRec(arr, index, n, n);

}

  

  
// драйверная программа

int main()

{

    int arr[] = { 3, 2, 999, 1 };

    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, n);

    return 0;

}

Джава

// Java программа для сортировки массива путем перемещения
// пространство вокруг.

  

class GFG

{

  
// n - общее количество элементов.
// индекс - это индекс 999 или пробел.
// k - количество элементов, которые еще предстоит отсортировать.

static void sortRec(int arr[], int index, int k, int n) 

    // выводим отсортированный массив при достижении цикла

    // базовый случай

    if (k == 0)

    

        for (int i = 1; i < n; i++) 

                        System.out.print(arr[i] + " "); 

                System.out.println(999); 

        return

    

  

    // иначе, если k> 0 и пробел находится в 0-м индексе

    // каждый номер с пробелом и сохранением индекса в

    // второй последний индекс

    else if (k > 0 && index == 0)

    

        index = n - 2

        for (int i = 1; i <= index; i++)

        

            arr[i - 1] = arr[i]; 

        

        arr[index] = 999

    

  

    // если пробел не является ни началом массива, ни последним

    // элемент массива и элемент перед ним больше

    // чем / элемент рядом с пробелом

    if (index - 1 >= 0 && index + 1 < n && 

    arr[index - 1] > arr[index + 1])

    

  

        // первый обмен пространства и элемент рядом с пробелом

        // в случае {3, 999, 2} сделать это {3, 2, 999}

        swap(arr,index, index + 1); 

  

        // чем пространство подкачки и больший элемент

        // преобразовать {3, 2, 999} в {999, 2, 3}

        swap(arr,index - 1, index + 1); 

    

  

    else

        swap(arr,index, index - 1); 

  

    sortRec(arr, index - 1, k - 1, n); 

  

static int[] swap(int []arr, int i, int j)

{

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

    return arr;

}

  
// Обёртка над sortRec.

static void sort(int arr[], int n) 

    // Найти индекс пробела (или 999)

    int index = -1

    for (int i = 0; i < n; i++)

    

        if (arr[i] == 999)

        

            index = i; 

            break

        

    

  

    // Неверный Ввод

    if (index == -1

        return

  

    sortRec(arr, index, n, n); 

  

  
// Код драйвера

public static void main(String[] args)

{

    int arr[] = { 3, 2, 999, 1 }; 

    int n = arr.length; 

    sort(arr, n); 

}
}

  
// Этот код предоставлен Rajput-Ji

C #

// C # программа для сортировки массива путем перемещения одного
// пространство вокруг.

using System;

  

class GFG 

  
// n - общее количество элементов.
// индекс - это индекс 999 или пробел.
// k - количество элементов, которые еще предстоит отсортировать.

static void sortRec(int []arr, int index, int k, int n) 

    // выводим отсортированный массив при достижении цикла

    // базовый случай

    if (k == 0) 

    

        for (int i = 1; i < n; i++) 

                        Console.Write(arr[i] + " "); 

                Console.WriteLine(999); 

        return

    

  

    // иначе, если k> 0 и пробел находится в 0-м индексе

    // каждый номер с пробелом и сохранением индекса в

    // второй последний индекс

    else if (k > 0 && index == 0) 

    

        index = n - 2; 

        for (int i = 1; i <= index; i++) 

        

            arr[i - 1] = arr[i]; 

        

        arr[index] = 999; 

    

  

    // если пробел не является ни началом массива, ни последним

    // элемент массива и элемент перед ним больше

    // чем / элемент рядом с пробелом

    if (index - 1 >= 0 && index + 1 < n && 

    arr[index - 1] > arr[index + 1]) 

    

  

        // первый обмен пространства и элемент рядом с пробелом

        // в случае {3, 999, 2} сделать это {3, 2, 999}

        swap(arr,index, index + 1); 

  

        // чем пространство подкачки и больший элемент

        // преобразовать {3, 2, 999} в {999, 2, 3}

        swap(arr,index - 1, index + 1); 

    

  

    else

        swap(arr,index, index - 1); 

  

    sortRec(arr, index - 1, k - 1, n); 

  

static int[] swap(int []arr, int i, int j) 

    int temp = arr[i]; 

    arr[i] = arr[j]; 

    arr[j] = temp; 

    return arr; 

  
// Обёртка над sortRec.

static void sort(int []arr, int n) 

    // Найти индекс пробела (или 999)

    int index = -1; 

    for (int i = 0; i < n; i++) 

    

        if (arr[i] == 999) 

        

            index = i; 

            break

        

    

  

    // Неверный Ввод

    if (index == -1) 

        return

  

    sortRec(arr, index, n, n); 

  

  
// Код драйвера

public static void Main(String[] args) 

    int []arr = { 3, 2, 999, 1 }; 

    int n = arr.Length; 

    sort(arr, n); 


  
// Этот код предоставлен 29AjayKumar



Выход:

1 2 3 999

Сложность времени — O (n 2 )

Рекомендуемые посты:

Разрешается сортировка массива с заменой только по специальному элементу

0.00 (0%) 0 votes