Слияние массивов

Опубликовано Sep 30, 2011 в Массивы и строки | 11 коммент.

, , , ,

Дано два массива  А и В. Массив А имеет в конце области данных буфер достаточного размера, для того чтобы вместить массив В. Массивы отсортированы. Напишите метод слияния массивов А и В

 void my_sort_merging(int* a, const int* b, int size_a, int size_b)
{
  // ваш код
}

Критерии оценки

Кандидат должен продемонстрировать, что понимает ключевое слово задачи “ОТСОРТИРОВАНЫ” и знает основные  проблемы, которые возникают при разработке алгоритмов, связанных с сортировкой.

Ожидаемые вопросы

  1. Можно ли использовать дополнительную память?
  2. Что более приоритетно – экономия памяти или быстродействие?
  3. Каков предполагаемый размер сортируемых массивов?
  4. Можно ли использовать готовые решения из библиотеки STL?

Оценка результатов

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

 От программистов с опытом работы мы ожидаем услышать вопросы типа 1 – 3, суть которых уточнение требований к эффективности решения и критериях ее оценки. Очень хорошо, если при обсуждении этих вопросов кандидат продемонстрирует, что он видит несколько вариантов реализации и понимает преимущества и недостатки каждого. Вопрос 4 покажет, что кандидат знает готовые стандартные решения и готов их применять.

 Решение на C# по алгоритму из комментария, автор которого Саша Томах

 static void my_sort_merging(int[] a, int[] b, int size_a, int size_b)
        {
          int pa = size_a - 1;
          int pb = size_b - 1;
 
          for (int i = (size_a + size_b - 1); i >= 0; i--)
          {
            if (pa < 0)
              a[i] = b[pb--];
            else if (pb < 0)
              a[i] = a[pa--];
            else
            {
              if (a[pa] < b[pb])
                a[i] = b[pb--];
              else
                a[i] = a[pa--];
            }
          }
        }
  static void Main(string[] args)
  {
     int[] A = { 8, -1, 3, 5, 0, -45, -6, 13, 55, 22,
     //буфер заполнен нулями, их столько, сколько элементов в массиве B
                    0,  0,  0,  0,  0,  0,  0,  0,  0};
      Array.Sort(A, 0, 9);
 
      int[] B = { 5, -41, 3, 40, -45, -69, 13, -55, 522 };
      Array.Sort(B);
 
      int size_b = B.Length;
      int size_a = A.Length - size_b;
 
      my_sort_merging(A, B, size_a, size_b);
   }