Рубрики

Сортировка по возрастанию и убыванию массива

Конкурентное программирование, Массивы, Сортировка

При заданном K-возрастающем-убывающем массиве arr [] задача состоит в том, чтобы отсортировать данный массив. Говорят, что массив увеличивается-уменьшается-уменьшается, если элементы многократно увеличиваются до определенного индекса, после чего они уменьшаются, а затем снова увеличиваются, в общей сложности в K раз. Диаграмма ниже показывает 4-убывающий массив.

Пример:

Input: arr[] = {57, 131, 493, 294, 221, 339, 418, 458, 442, 190}
Output: 57 131 190 221 294 339 418 442 458 493

Input: arr[] = {1, 2, 3, 4, 3, 2, 1}
Output: 1 1 2 2 3 3 4

Подход. Метод грубой силы заключается в сортировке массива без использования свойства k-увеличения-уменьшения. Временная сложность этого подхода составляет O (n logn), где n — длина массива.

Если k значительно меньше, чем n, можно найти лучший подход с меньшей сложностью по времени. Например, если k = 2, входной массив состоит из двух подмассивов: один увеличивается, а другой уменьшается. Обращение второго подмассива дает два отсортированных массива, а затем результат объединяется, что можно сделать за O (n) раз. Обобщая, мы могли бы сначала изменить порядок каждого из убывающих подмассивов. Например, на приведенном выше рисунке массив может быть разбит на четыре отсортированных массива как {57, 131, 493}, {221, 294}, {339, 418, 458} и {190, 442}. Теперь метод с минимальной кучей может использоваться для объединения этих отсортированных массивов .

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

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// пара пар, первый элемент собирается
// сохранить значение, индекс второго элемента массива
// и индекс третьего элемента в массиве

typedef pair<int, pair<int, int> > ppi;

  
// Эта функция принимает массив массивов как
// аргумент и все массивы предполагаются
// отсортировано
// Объединяет их вместе и возвращает
// окончательно отсортированный вывод

vector<int> mergeKArrays(vector<vector<int> > arr)

{

    vector<int> output;

  

    // Создаем минимальную кучу с k узлами кучи

    // Каждый узел кучи имеет первый элемент массива

    priority_queue<ppi, vector<ppi>, greater<ppi> > pq;

  

    for (int i = 0; i < arr.size(); i++)

        pq.push({ arr[i][0], { i, 0 } });

  

    // Теперь один за другим получаем минимальный элемент

    // из минимальной кучи и заменить его следующим

    // элемент его массива

    while (pq.empty() == false) {

        ppi curr = pq.top();

        pq.pop();

  

        // я ==> номер массива

        // j ==> Индекс в номере массива

        int i = curr.second.first;

        int j = curr.second.second;

  

        output.push_back(curr.first);

  

        // Следующий элемент принадлежит тому же массиву, что и

        // текущий

        if (j + 1 < arr[i].size())

            pq.push({ arr[i][j + 1], { i, j + 1 } });

    }

  

    return output;

}

  
// Функция для сортировки чередующихся
// растущий-убывающий массив

vector<int> SortKIncDec(const vector<int>& A)

{

    // Разложить массив в

    // набор отсортированных массивов

    vector<vector<int> > sorted_subarrays;

    typedef enum { INCREASING,

                   DECREASING } SubarrayType;

    SubarrayType subarray_type = INCREASING;

    int start_idx = 0;

    for (int i = 0; i <= A.size(); i++) {

  

        // Если текущие подмассивы заканчиваются здесь

        if (i == A.size()

            || (A[i - 1] < A[i]

                && subarray_type == DECREASING)

            || (A[i - 1] >= A[i]

                && subarray_type == INCREASING)) {

  

            // Если подрешетка увеличивается

            // затем добавляем с самого начала

            if (subarray_type == INCREASING) {

                sorted_subarrays.emplace_back(A.cbegin() + start_idx,

                                              A.cbegin() + i);

            }

  

            // Если подрешетка уменьшается

            // затем добавляем с конца

            else {

                sorted_subarrays.emplace_back(A.crbegin()

                                                  + A.size() - i,

                                              A.crbegin()

                                                  + A.size()

                                                  - start_idx);

            }

            start_idx = i;

            subarray_type = (subarray_type == INCREASING

                                 ? DECREASING

                                 : INCREASING);

        }

    }

  

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

    return mergeKArrays(sorted_subarrays);

}

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

int main()

{

    vector<int> arr = { 57, 131, 493, 294, 221,

                        339, 418, 458, 442, 190 };

  

    // Получить отсортированный массив

    vector<int> ans = SortKIncDec(arr);

  

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

    for (int i = 0; i < ans.size(); i++)

        cout << ans[i] << " ";

  

    return 0;

}

Выход:

57 131 190 221 294 339 418 442 458 493

Сложность времени: O (n * logk), где n — длина массива.

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

Сортировка по возрастанию и убыванию массива

0.00 (0%) 0 votes