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

Опубликовано 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);
   }

11 Коммент. : “Слияние массивов”

  1. Простое решение, не требующее выделения дополнительной памяти, однако не самое лучшее по быстродействию:

    void MergeSortedArrays(int* a, int* b, int size_a, int size_b)
    {
    	int maxElemId_a = GetMaxElemID(a, size_a);
    	int aIdx, bIdx;
    	aIdx = bIdx = 0;
    	while(bIdx < size_b)
    	{
    		if(aIdx > maxElemId_a)
    		// Array a is over, array b still has elements.
    		// We will write the rest elements from b to
    		// the end of array a
    		{
    			for(; bIdx < size_b; aIdx++, bIdx++)
    			{
    				a[aIdx] = b[bIdx];
    			}
    		}
    		else
    		// Elements in both arrays left
    		{
    			if(b[bIdx] <= a[aIdx])
    			{
    				for(int i = maxElemId_a; i >= aIdx; i--)
    				{
    					a[i+1] = a[i];
    				}
    				maxElemId_a++;
    				a[aIdx] = b[bIdx];
    				bIdx++;
    			}
    			aIdx++;
    		}
    	}
    }
     
    int GetMaxElemID(int arr[], int nElem)
    {
    	int maxElemId = nElem-1;
    	for(int i = nElem-2; i >= 0; i--)
    	{
    		if(arr[i] > arr[maxElemId])
    		{
    			maxElemId = i;
    		}
    	}
    	return maxElemId;
    }
  2. Более лёгкое для восприятия решение с выделением дополнительной памяти.

    void MergeSortedArrays_AddMemory(int* a, int* b, int size_a, int size_b)
    {
    	int *finalArray = new int[size_a];
    	int aIdx, bIdx, finalIdx;
    	aIdx = bIdx = finalIdx = 0;
    	int maxElemId_a = GetMaxElemID(a, size_a);
    	while(finalIdx < size_a)
    	{
    		if(aIdx > maxElemId_a)
    			// Array a is over, array b still has elements.
    			// We will write the rest elements from b to
    			// the final array
    		{
    			for(; bIdx < size_b; finalIdx++, bIdx++)
    			{
    				finalArray[finalIdx] = b[bIdx];
    			}
    		}
    		else if (bIdx >= size_b)
    			// Array b is over, array a still has elements.
    			// We will write the rest elements from a to
    			// the final array
    		{
    			for(; aIdx < size_a; finalIdx++, aIdx++)
    			{
    				finalArray[finalIdx] = a[aIdx];
    			}
    		}
    		else
    			// Both arrays has unprocessed elements
    		{
    			if(a[aIdx] <= b[bIdx])
    			{
    				finalArray[finalIdx] = a[aIdx];
    				aIdx++;
    			}
    			else
    			{
    				finalArray[finalIdx] = b[bIdx];
    				bIdx++;
    			}
    			finalIdx++;
    		}
    	}
    	for(int i = 0; i < size_a; i++)
    	{
    		a[i] = finalArray[i];
    	}
    	delete [] finalArray;
    }
  3. Саша Томах says:

    А теперь внимание правильный ответ! Единственный алгоритм, удовлетворяющий (на мой взгляд) сразу всем условиям должен проходить по массиву А не с начала, а с конца и выглядеть примерно так:

    void my_sort_merging(int * a, const 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--];
    		}
    	}
    }
    • Галина says:

      Да, решение, похоже работоспособно. Тестовый вызов, написанный на C#, перенесен в верхнюю часть поста.

  4. Дмитрий Храмов says:

    На мой взгляд, добавочной экономии можно добиться, выбрав в качестве условия окончания цикла исчерпание массива b. Тогда оставшиеся элементы a просто остаются на своих местах.

    с-код (size_a – длина а с учетом буфера):

    #include <stdio.h>
     
    const int size_a = 19;
    const int size_b = 9;
     
    void my_sort_merging(int* a, const int* b, int size_a, int size_b)
    {
      int i  = size_a-1;
      int ib = size_b-1;
      int ia = size_a-size_b-1;
     
      for ( ; ib >= 0; i--) {
        if (ia >= 0) {
          if (b[ib] > a[ia])
            a[i] = b[ib--];
          else
            a[i] = a[ia--];
        }
        else
            a[i] = b[ib--];
      }
    }
     
    int main()
    {
      int b[size_b] = { -69, -55, -45, -41, 3, 5, 13, 40, 522 };
      int a[size_a] = { -45, -6, -1, 0, 3, 5, 8, 13, 22, 55, 0 };
     
      my_sort_merging(a, b, size_a, size_b);
     
      return 0;
    }
  5. Игорь says:

    #include

    void my_sort_merging(int* a, const int* b, int size_a, int size_b)
    {
    int ndx = 0;
    while(ndx < size_b) a[size_a + ndx++] = b[ndx];
    }

    int main(){
    int a1[20] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int a2[10] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
    my_sort_merging(a1, a2, 10, 10);
    for(int i = 0; i < 20; i++)
    std::cout << “a1[" << i << "] = ” << a1[i] << std::endl;
    return 0;
    }

  6. Игорь says:

    //слияние простой вставкой для небольших массивов

    #include <iostream>
     
    using std::cout;
    using std::end;
     
    void my_sort_merging(int* a, const int* b, int size_a, int size_b)
    {
    	for(int i = 0; i < size_b; i++){
    		int temp = b[i];
    		int j;
    		for(j = size_a + i - 1; j >= 0 && a[j] > temp; j--)
    			a[j + 1] = a[j];
    		a[j + 1] = temp;
    	}
    }
     
    int main(){
    	int a1[20] = { 0, 1, 2, 3, 4, 5, 6, 17, 23, 29};
    	int a2[10] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 24};
    	my_sort_merging(a1, a2, 10, 10);
    	for(int i = 0; i < 20; i++)
    		std::cout << "a1[" << i << "] = " << a1[i] << std::endl;
    	return 0;
    }
  7. Игорь says:

    бинарной вставкой для больших массивов

    #include <iostream>
     
    template<class T>
    void binInsert(T* arr, int low, int hight, const T& key){
    	int middle;
    	int border = hight;
    	while(low < hight){
    		middle = (low + hight) / 2;
    		if(arr[middle] > key) hight = middle; else low = middle + 1;
    	}
    	for(int j = border; j >= low; j--)
    		arr[j + 1] = arr[j];
    	arr[low] = key;
    }
     
    void my_sort_merging(int* a, const int* b, int size_a, int size_b)
    {
    	for(int i = 0; i < size_b; i++){
    		int temp = b[i];
    		binInsert(a, 0, size_a + i - 1, temp);
    	}
    }
     
    int main(){
    	int a1[20] = { 0, 1, 2, 3, 4, 5, 6, 17, 23, 29};
    	int a2[10] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 24};
    	my_sort_merging(a1, a2, 10, 10);
    	for(int i = 0; i < 20; i++)
    		std::cout << "a1[" << i << "] = " << a1[i] << std::endl;
    	return 0;
    }
  8. Задача поставлена НЕВЕРНО!
    Ничего не написано о том, что результирующий массив должен быть так же отсортирован!

    следовательно и неверное решение..
    Мержит два массива – задача выполнена)))

    int b[4]={1,2,3,4};
    int a[8]={3,4,5,6,0,0,0,0};

    size_t bsize = 4;
    const int *bo = b;
    int *ao = a + bsize;
    for(int r = 0;r < bsize;r++,ao++,bo++)
    *ao = *bo;

  9. Артур says:
    void my_sort_merging(int* a, const int* b, int size_a, int size_b){
    	int newj = 0;
    	int *ptr = nullptr;
    	for(int i = 0; i < size_b; i++){
    		for(int j = newj; j < size_a; j++){
    			ptr = a + (size_a - size_b) + i;
    			if(*(b+i) < *(a+j) && a+j != ptr){
    				copy(a+j, a+(size_a - (size_b - i)), a+j+1);
    				*(a+j) = *(b+i);
    				for_each(a,a+size_a,show);cout<<endl;
    				newj = j + 1;
    				break;
    			}
    			if(a+j == ptr && ptr != a+size_a){
    				*(a+j) = *(b+i);
    				for_each(a,a+size_a,show);cout<<endl;
    				break;
    			}
    		}
    	}
    	ptr = nullptr;
    }
  10. Владислав says:
     
    // для корректной работы нужно передавать количество элементов
    // массива А, а не полный размер
    void my_sort_merging(int* a, int* b, int size_a, int size_b) {
     
        int start;
        // поскольку массивы отсортированы определяем с какой точки 
        // нужно начать слияние
        for(int i=0; i<size_a; i++)
            if(a[i] > b[0]){
                start = i;
                break;
            }
     
        for(int i = start; i<size_a; i++)
            for(int j = 0; j <size_b; j++)
                {
                if(a[i] > b[j])
                    std::swap(a[i],b[j]);
                }
     
    // массив В теперь отсортирован и строго меньше массива А,    
    // поэтому просто записываем все в конец массива А
     
        for(int i = size_a, j = 0; j < size_b; i++, j++)
            a[i] = b[j];
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*