Слияние двух упорядоченных массивов (реализация на C++)

C++   21 февраля 2012  Автор статьи:  

Приведем пример реализации алгоритма слияния двух упорядоченных массивов в один. На входе алгоритм получает два отсортированных массива, которые задаются своим размером и элементами типа int. На выходе алгоритм выводит упорядоченный массив, состоящий из всех элементов двух исходных.

Этот алгоритм является основой для весьма эффективного алгоритма сортировки, который называется сортировка слиянием (merge sort) и имеет алгоритмическую сложность O(n*log(n)). Сложность же алгоритма слияния двух упорядоченных массивов составляет O(n+m), где n и m — соответственно размеры заданных массивов.


#include
using namespace std;

int main()
{
// Считываем размеры массивов,
// который необходимо слить в
// один отсортированный массив
int n, m;
cin >> n >> m;

// Динамически выделяем память под
// хранение массивов размера n и m
int *a = new int[n];
int *b = new int[m];

// Считываем массивы;
// По условию алгоритма они уже
// должны быть отсортированы
for (int i = 0; i < n; i++) { cin >> a[i];
}

for (int i = 0; i < m; i++) { cin >> b[i];
}

// Динамически выделяем память под
// хранение массива, полученного
// слиянием двух исходных, его
// размер, очевидно, равен n + m
int *result = new int[n + m];

// Заведем два индекса, указывающих
// на первый необработанный элемент
// первого и второго массивов
int i = 0, j = 0;

// И заведем индекс массива-результата,
// который указывает позицию, которая
// будет заполнена на текущем шаге
int index = 0;

// Будем повторять сравнение элементов
// массивов a и b до тех пор, пока
// в каждом из них есть хотя бы один
// необработанный элемент
while (i < n && j < m) { // В соответствии с тем, текущий элемент // какого массива меньше, мы записываем // этот элемент в массив-результат и // обновляем нужный индекс (i или j) if (a[i] < b[j]) { result[index] = a[i]; i++; } else { result[index] = b[j]; j++; } index++; } // После выполнения предыдущего цикла // все элементы одного из массивов будут // обработаны, тогда оставшиеся элементы // другого массива нужно просто дописать // в массив-результат // Заметим, что одно из условий (i < n) // или (j < m) будет гарантированно ложно while (i < n) { result[index] = a[i]; index++; i++; } while (j < m) { result[index] = b[j]; index++; j++; } // Выводим отсортированный массив for (int k = 0; k < n + m; k++) { cout << result[k] << ' '; } return 0; }

  • Belka

    В алгоритме что-то не так… сделала, как здесь — выдает на 1 значение больше, чем n+m, кот. не заполнено. будет работать правильно, если перед выводом result [index] на экран поставить index—, так как после последнего прохода цикла значение index = n + m + 1.
    вот код:

    int Sliyanie (int *a, int *b, int size, int size2){    int *result = new int [size+size2];    int i = 0, j = 0; // два индекса, указывающих на первый необработанный элемент первого и второго массивов    int index = 0; //индекс массива-результата, который указывает позицию, которая будет заполнена на текущем шаге    while (i < size && j < size2)    {      if (a [i] < b [j])     {        result [index] = a [i];         i++;      }      else     {         result [index] = b [j];         j++;      }      index++;     }    while (i < size)    {        result[index] = a[i];        index++;        i++;     }      while (j < size)      {         result[index] = b[j];         index++;         j++;      }    index—;    for (int k = 0; k <= (index); k++)     cout<< result [k]<<"t";     cout<<"nn";     return result[index];}

    • Lordrp

      Ты случайно в Warcraft3 не играла?) Не знаю на счет тут (скорей всего все правильно, просто ты чего — то не так делаешь, значение index после последнего такое и должно быть, потому что присваивание делается до него) У меня в алгоритме сортировки слиянием, эта функция написана попроще и точно правильно)

  • Belka

    В алгоритме что-то не так… сделала, как здесь — выдает на 1 значение больше, чем n+m, кот. не заполнено. будет работать правильно, если перед выводом result [index] на экран поставить index—, так как после последнего прохода цикла значение index = n + m + 1.
    вот код:

    int Sliyanie (int *a, int *b, int size, int size2){    int *result = new int [size+size2];    int i = 0, j = 0; // два индекса, указывающих на первый необработанный элемент первого и второго массивов    int index = 0; //индекс массива-результата, который указывает позицию, которая будет заполнена на текущем шаге    while (i < size && j < size2)    {      if (a [i] < b [j])     {        result [index] = a [i];         i++;      }      else     {         result [index] = b [j];         j++;      }      index++;     }    while (i < size)    {        result[index] = a[i];        index++;        i++;     }      while (j < size)      {         result[index] = b[j];         index++;         j++;      }    index—;    for (int k = 0; k <= (index); k++)     cout<< result [k]<<"t";     cout<<"nn";     return result[index];}

    • Lordrp

      Ты случайно в Warcraft3 не играла?) Не знаю на счет тут (скорей всего все правильно, просто ты чего — то не так делаешь, значение index после последнего такое и должно быть, потому что присваивание делается до него) У меня в алгоритме сортировки слиянием, эта функция написана попроще и точно правильно)

Научиться программировать

  • на Delphi

  • на Java

  • на C++