Рубрики

Сортировать массив, когда две половинки отсортированы

Дан целочисленный массив, из которого отсортированы как первая половина, так и вторая половина. Задача состоит в том, чтобы объединить две отсортированные половины массива в один отсортированный массив.

Примеры:

Input : A[] = { 2, 3, 8, -1, 7, 10 }
Output : -1, 2, 3, 7, 8, 10 

Input : A[] = {-4, 6, 9, -1, 3 }
Output : -4, -1, 3, 6, 9 

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

C ++

// C ++ программа для объединения двух отсортированных половинок
// массив в один отсортированный массив
#include <bits/stdc++.h>

using namespace std;

  

void mergeTwoHalf(int A[], int n)

{

    // Сортировка указанного массива с использованием сортировки STL

    sort(A, A + n);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int A[] = { 2, 3, 8, -1, 7, 10 };

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

    mergeTwoHalf(A, n);

  

    // Распечатать отсортированный массив

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

        cout << A[i] << " ";

    return 0;

}

Джава

// Java-программа для объединения двух отсортированных половинок
// массив в один отсортированный массив

import java.io.*;

import java.util.*;

  

class GFG {

  

    static void mergeTwoHalf(int[] A, int n)

    {

        // Сортировка указанного массива с использованием сортировки STL

        Arrays.sort(A);

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    static public void main(String[] args)

    {

        int[] A = { 2, 3, 8, -1, 7, 10 };

        int n = A.length;

        mergeTwoHalf(A, n);

  

        // Распечатать отсортированный массив

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

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

    }

}

  
// Этот код предоставлен vt_m.

python3

# Python3 программа для объединения двух отсортированных
# половин массива в один отсортированный массив

  

def mergeTwoHalf(A, n):

      

    # Сортировать указанный массив, используя сортировку STL

    A.sort()

  
Код водителя

if __name__ == '__main__':

    A = [ 2, 3, 8, -1, 7, 10 ]

    n= len(A)

    mergeTwoHalf(A, n)

  

    # Распечатать отсортированный массив

    for i in range(n):

        print(A[i], end = " ")

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

C #

// C # программа для объединения двух отсортированных половинок
// массив в один отсортированный массив

using System;

  

class GFG {

  

    static void mergeTwoHalf(int[] A, int n)

    {

        // Сортировка указанного массива с использованием сортировки STL

        Array.Sort(A);

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    static public void Main()

    {

        int[] A = {2, 3, 8, -1, 7, 10};

        int n = A.Length;

        mergeTwoHalf(A, n);

  

        // Распечатать отсортированный массив

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

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

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для объединения двух отсортированных половинок
// массива в один отсортированный массив

  

function mergeTwoHalf(&$A, $n)

{

    // Сортировка указанного массива с использованием сортировки STL

    sort($A, 0);

}

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

$A = array(2, 3, 8, -1, 7, 10);

$n = sizeof($A);

mergeTwoHalf($A, $n);

  
// Распечатать отсортированный массив

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

    echo $A[$i] . " ";

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

-1 2 3 7 8 10  

Сложность времени O (nlogn) || Сортировать данный массив с помощью быстрой сортировки или сортировки слиянием

Эффективное решение — использовать вспомогательный массив наполовину. Теперь весь процесс аналогичен функции слияния сортировки слиянием .
Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для объединения двух отсортированных половинок
// Array Into Single Sorted Array
#include <bits/stdc++.h>

using namespace std;

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

void mergeTwoHalf(int A[], int n)

{

    int half_i = 0; // начальный индекс второй половины

  

    // Temp Array store отсортированный результирующий массив

    int temp[n];

  

    // Сначала найти точку, где массив делится

    // на две половины

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

        if (A[i] > A[i + 1]) {

            half_i = i + 1;

            break;

        }

    }

  

    // если данный массив полностью готов отсортирован

    if (half_i == 0)

        return;

  

    // Объединяем два отсортированных массива в один отсортированный массив

    int i = 0, j = half_i, k = 0;

    while (i < half_i && j < n) {

        if (A[i] < A[j])

            temp[k++] = A[i++];

        else

            temp[k++] = A[j++];

    }

  

    // Копируем оставшиеся элементы A [i в half_! ]

    while (i < half_i)

        temp[k++] = A[i++];

  

    // Копируем оставшиеся элементы A [half_! на п]

    while (j < n)

        temp[k++] = A[j++];

  

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

        A[i] = temp[i];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int A[] = { 2, 3, 8, -1, 7, 10 };

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

    mergeTwoHalf(A, n);

  

    // Распечатать отсортированный массив

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

        cout << A[i] << " ";

    return 0;

}

Джава

// Java-программа для объединения двух отсортированных половинок
// Array Into Single Sorted Array

import java.io.*;

  

class GFG {

  

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

    // в один отсортированный массив

    static void mergeTwoHalf(int[] A, int n)

    {

        int half_i = 0; // начальный индекс второй половины

        int i;

          

        // Temp Array store отсортированный результирующий массив

        int[] temp = new int[n];

  

        // Сначала найти точку, где массив делится

        // на две половины

        for (i = 0; i < n - 1; i++) {

            if (A[i] > A[i + 1]) {

                half_i = i + 1;

                break;

            }

        }

  

        // если данный массив полностью готов отсортирован

        if (half_i == 0)

            return;

  

        // Объединяем два отсортированных массива в один отсортированный массив

        i = 0;

        int j = half_i;

        int k = 0;

        while (i < half_i && j < n) {

            if (A[i] < A[j])

                temp[k++] = A[i++];

            else

                temp[k++] = A[j++];

        }

  

        // Копируем оставшиеся элементы A [i в half_! ]

        while (i < half_i)

            temp[k++] = A[i++];

  

        // Копируем оставшиеся элементы A [half_! на п]

        while (j < n)

            temp[k++] = A[j++];

  

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

            A[i] = temp[i];

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    static public void main(String[] args)

    {

        int[] A = {2, 3, 8, -1, 7, 10};

        int n = A.length;

        mergeTwoHalf(A, n);

  

        // Распечатать отсортированный массив

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

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

    }

}

  
// Этот код предоставлен vt_m.

C #

// C # программа для объединения двух отсортированных половинок
// Array Into Single Sorted Array

using System;

  

class GFG {

  

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

    // в один отсортированный массив

    static void mergeTwoHalf(int[] A, int n)

    {

        int half_i = 0; // начальный индекс второй половины

        int i;

          

        // Temp Array store отсортированный результирующий массив

        int[] temp = new int[n];

  

        // Сначала найти точку, где массив делится

        // на две половины

        for (i = 0; i < n - 1; i++) {

            if (A[i] > A[i + 1]) {

                half_i = i + 1;

                break;

            }

        }

  

        // если данный массив полностью готов отсортирован

        if (half_i == 0)

            return;

  

        // Объединяем два отсортированных массива в один отсортированный массив

        i = 0;

        int j = half_i;

        int k = 0;

        while (i < half_i && j < n) {

            if (A[i] < A[j])

                temp[k++] = A[i++];

            else

                temp[k++] = A[j++];

        }

  

        // Копируем оставшиеся элементы A [i в half_! ]

        while (i < half_i)

            temp[k++] = A[i++];

  

        // Копируем оставшиеся элементы A [half_! на п]

        while (j < n)

            temp[k++] = A[j++];

  

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

            A[i] = temp[i];

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    static public void Main()

    {

        int[] A = { 2, 3, 8, -1, 7, 10 };

        int n = A.Length;

        mergeTwoHalf(A, n);

  

        // Распечатать отсортированный массив

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

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

    }

}

  
// Этот код предоставлен vt_m.


Выход:

-1 2 3 7 8 10 

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

Ссылка: https://www.careercup.com/question?id=8412257

Эта статья предоставлена Nishant Singh . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Сортировать массив, когда две половинки отсортированы

0.00 (0%) 0 votes