Рубрики

Сортировать массив в форме волны

Учитывая несортированный массив целых чисел, отсортируйте массив в виде волны, как массив. Массив 'arr [0..n-1]' сортируется в форме волны, если arr [0]> = arr [1] = arr [3] =… ..

Примеры:

 Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
 Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR
                 {20, 5, 10, 2, 80, 6, 100, 3} OR
                 any other array that is in wave form

 Input:  arr[] = {20, 10, 8, 6, 4, 2}
 Output: arr[] = {20, 8, 10, 4, 6, 2} OR
                 {10, 8, 20, 2, 6, 4} OR
                 any other array that is in wave form

 Input:  arr[] = {2, 4, 6, 8, 10, 20}
 Output: arr[] = {4, 2, 8, 6, 20, 10} OR
                 any other array that is in wave form

 Input:  arr[] = {3, 6, 5, 10, 7, 20}
 Output: arr[] = {6, 3, 10, 5, 20, 7} OR
                 any other array that is in wave form

Простое решение — использовать сортировку. Сначала отсортируйте входной массив, затем поменяйте местами все смежные элементы.

Например, пусть входной массив будет {3, 6, 5, 10, 7, 20}. После сортировки получаем {3, 5, 6, 7, 10, 20}. После замены соседних элементов получаем {5, 3, 7, 6, 20, 10}.

Ниже приведены реализации этого простого подхода.

C ++

// Программа на C ++ для сортировки массива в форме волны с использованием
// сортирующая функция
#include<iostream>
#include<algorithm>

using namespace std;

  
// Утилита для обмена двумя числами.

void swap(int *x, int *y)

{

    int temp = *x;

    *x = *y;

    *y = temp;

}

  
// Эта функция сортирует arr [0..n-1] в форме волны, т.е.
// arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4]> = arr [5] ..

void sortInWave(int arr[], int n)

{

    // Сортировка входного массива

    sort(arr, arr+n);

  

    // Меняем местами соседние элементы

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

        swap(&arr[i], &arr[i+1]);

}

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

int main()

{

    int arr[] = {10, 90, 49, 2, 1, 5, 23};

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

    sortInWave(arr, n);

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

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

    return 0;

}

Джава

// Java реализация наивного метода для сортировки
// массив в форме волны.

import java.util.*;

  

class SortWave

{

    // Утилита для обмена двумя числами.

    void swap(int arr[], int a, int b)

    {

        int temp = arr[a];

        arr[a] = arr[b];

        arr[b] = temp;

    }

  

    // Эта функция сортирует arr [0..n-1] в форме волны, т.е.

    // arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4] ..

    void sortInWave(int arr[], int n)

    {

        // Сортировка входного массива

        Arrays.sort(arr);

  

        // Меняем местами соседние элементы

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

            swap(arr, i, i+1);

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        SortWave ob = new SortWave();

        int arr[] = {10, 90, 49, 2, 1, 5, 23};

        int n = arr.length;

        ob.sortInWave(arr, n);

        for (int i : arr)

            System.out.print(i + " ");

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Функция Python для сортировки массива arr [0..n-1] в форме волны,
# т.е. arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4]> = arr [5]

def sortInWave(arr, n):

      

    # сортировать массив

    arr.sort()

     

    # Поменяйте местами соседние элементы

    for i in range(0,n-1,2):

        arr[i], arr[i+1] = arr[i+1], arr[i]

  
# Драйвер прогрМ

arr = [10, 90, 49, 2, 1, 5, 23]

sortInWave(arr, len(arr))

for i in range(0,len(arr)):

    print arr[i],

      
# Этот код предоставлен __Devesh Agrawal__

C #

// C # реализация наивного метода
// для сортировки массива в форме волны.

using System;

  

class SortWave {

      

    // Утилита для обмена двумя числами.

    void swap(int[] arr, int a, int b)

    {

        int temp = arr[a];

        arr[a] = arr[b];

        arr[b] = temp;

    }

  

    // Эта функция сортирует arr [0..n-1] в форме волны, т.е.

    // arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4] ..

    void sortInWave(int[] arr, int n)

    {

        // Сортировка входного массива

        Array.Sort(arr);

  

        // Меняем местами соседние элементы

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

            swap(arr, i, i + 1);

    }

  

    // Метод драйвера

    public static void Main()

    {

        SortWave ob = new SortWave();

        int[] arr = { 10, 90, 49, 2, 1, 5, 23 };

        int n = arr.Length;

          

        ob.sortInWave(arr, n);

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

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

    }

}

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


Выход:

2 1 10 5 49 23 90

Временная сложность вышеупомянутого решения составляет O (nLogn), если используется алгоритм сортировки O (nLogn), такой как сортировка слиянием, сортировка кучи и т. Д.

Это можно сделать за O (n) раз, выполнив одиночный обход заданного массива. Идея основана на том факте, что если мы убедимся, что все элементы с четным позиционированием (с индексами 0, 2, 4, ..) больше, чем их соседние нечетные элементы, нам не нужно беспокоиться о элементе с нечетным позиционированием. Ниже приведены простые шаги.
1) Пройдите через все четные элементы входного массива и выполните следующее.
… .A) Если текущий элемент меньше предыдущего нечетного элемента, поменяйте местами предыдущий и текущий.
… .B) Если текущий элемент меньше следующего нечетного элемента, поменяйте местами следующий и текущий.

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

C ++

// AO (n) программа для сортировки входного массива в форме волны
#include<iostream>

using namespace std;

  
// Утилита для обмена двумя числами.

void swap(int *x, int *y)

{

    int temp = *x;

    *x = *y;

    *y = temp;

}

  
// Эта функция сортирует arr [0..n-1] в форме волны, т.е. arr [0]> =
// arr [1] <= arr [2]> = arr [3] <= arr [4]> = arr [5] ....

void sortInWave(int arr[], int n)

{

    // Обходить все четные элементы

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

    {

        // Если текущий четный элемент меньше предыдущего

        if (i>0 && arr[i-1] > arr[i] )

            swap(&arr[i], &arr[i-1]);

  

        // Если текущий четный элемент меньше следующего

        if (i<n-1 && arr[i] < arr[i+1] )

            swap(&arr[i], &arr[i + 1]);

    }

}

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

int main()

{

    int arr[] = {10, 90, 49, 2, 1, 5, 23};

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

    sortInWave(arr, n);

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

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

    return 0;

}

Джава

// AO (n) Java-программа для сортировки входного массива в форме волны

class SortWave

{

    // Утилита для обмена двумя числами.

    void swap(int arr[], int a, int b)

    {

        int temp = arr[a];

        arr[a] = arr[b];

        arr[b] = temp;

    }

  

    // Эта функция сортирует arr [0..n-1] в форме волны, т.е.

    // arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4] ....

    void sortInWave(int arr[], int n)

    {

        // Обходить все четные элементы

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

        {

            // Если текущий четный элемент меньше

            // чем предыдущий

            if (i>0 && arr[i-1] > arr[i] )

                swap(arr, i-1, i);

  

            // Если текущий четный элемент меньше

            // затем

            if (i<n-1 && arr[i] < arr[i+1] )

                swap(arr, i, i + 1);

        }

    }

  

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

    public static void main(String args[])

    {

        SortWave ob = new SortWave();

        int arr[] = {10, 90, 49, 2, 1, 5, 23};

        int n = arr.length;

        ob.sortInWave(arr, n);

        for (int i : arr)

            System.out.print(i+" ");

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Функция Python для сортировки массива arr [0..n-1] в форме волны,
# т.е. arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4]> = arr [5]

def sortInWave(arr, n):

      

    # Пройти все четные элементы

    for i in range(0, n, 2):

          

        # Если текущий четный элемент меньше предыдущего

        if (i> 0 and arr[i] < arr[i-1]):

            arr[i],arr[i-1] = arr[i-1],arr[i]

          

        # Если текущий четный элемент меньше следующего

        if (i < n-1 and arr[i] < arr[i+1]):

            arr[i],arr[i+1] = arr[i+1],arr[i]

  
# Драйверная программа

arr = [10, 90, 49, 2, 1, 5, 23]

sortInWave(arr, len(arr))

for i in range(0,len(arr)):

    print arr[i],

      
# Этот код предоставлен __Devesh Agrawal__

C #

// AO (n) C # программа для сортировки
// входной массив в форме волны

using System;

  

class SortWave {

      

    // Утилита для обмена двумя числами.

    void swap(int[] arr, int a, int b)

    {

        int temp = arr[a];

        arr[a] = arr[b];

        arr[b] = temp;

    }

  

    // Эта функция сортирует arr [0..n-1] в форме волны, т.е.

    // arr [0]> = arr [1] <= arr [2]> = arr [3] <= arr [4] ....

    void sortInWave(int[] arr, int n)

    {

        // Обходить все четные элементы

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

              

            // Если текущий четный элемент меньше

            // чем предыдущий

            if (i > 0 && arr[i - 1] > arr[i])

                swap(arr, i - 1, i);

  

            // Если текущий четный элемент меньше

            // затем

            if (i < n - 1 && arr[i] < arr[i + 1])

                swap(arr, i, i + 1);

        }

    }

  

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

    public static void Main()

    {

        SortWave ob = new SortWave();

        int[] arr = { 10, 90, 49, 2, 1, 5, 23 };

        int n = arr.Length;

          

        ob.sortInWave(arr, n);

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

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

    }

}

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

Выход:

90 10 49 1 5 2 23

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

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

Сортировать массив в форме волны

0.00 (0%) 0 votes