Сортировка: вариации на тему (продолжение)

Опубликовано Sep 24, 2012 в Массивы и строки | 4 коммент.

, ,

Сортировка: вариации на тему (продолжение)

Из комментария к предыдущему посту про сортировку.
Есть задачка поинтересней – как слить два уже отсортированных массива, сохранив порядок сортировки, не вызывая при этом Sort/OrderBy ни в каком виде? И сложность хочется линейную.

Обратите внимание. Эта задача не тождественна задаче из поста /archives/1018, так как в данном варианте слияние происходит в новый массив – размер буфера здесь равен сумме размерностей исходных массивов.

Вот решение.

        public static int[] merge(int[] A, int[] B)
        {
            int[] result = new int[A.Length + B.Length];
            int aIndex = 0;
            int bIndex = 0;
            while (aIndex + bIndex != result.Length)
            {
                if (aIndex == A.Length)
                {
                    result[aIndex + bIndex] = B[bIndex];
                    ++bIndex;
                    continue;
                }
 
                if (bIndex == B.Length)
                {
                    result[aIndex + bIndex] = A[aIndex];
                    ++aIndex;
                    continue;
                }
 
                if (A[aIndex] < B[bIndex])
                {
                    result[aIndex + bIndex] = A[aIndex];
                    ++aIndex;
                }
                else
                {
                    result[aIndex + bIndex] = B[bIndex];
                    ++bIndex;
                }
            }
            return result;
        }
 
        static void Main(string[] args)
        {
            //test data
            int[] A = { 8, -1, 3, 5, 0, -45, -6, 13, 55, 22 };
            Array.Sort(A);
            int[] B = { 5, -41, 3, 40, -45, -69, 13, -55, 522 };
            Array.Sort(B);
 
            //call
            int[] merged = merge(A, B);
        }

Автор публикации:

4 Коммент. : “Сортировка: вариации на тему (продолжение)”

  1. Александр says:
    static void Main(string[] args)
            {
                //test data
                int[] A = { 8, -1, 3, 5, 0, -45, -6, 13, 55, 22 };
                Array.Sort(A);
                int[] B = { 5, -41, 3, 40, -45, -69, 13, -55, 522 };
                Array.Sort(B);
     
                //call
                int[] merged = A.Concat(B);
            }
    • Галина says:

      К сожалению, здесь все неверно.

      1) В посте предлагалось найти решение, не используя Sort ни в каком виде.
      2) Этот код не скомпилируется – ошибка здесь
      int[] merged = A.Concat(B);
      LINQ требует явного приведения IEnumerable к Array. Нужно так

      IEnumerable<int> merged = A.Concat(B);
      int[] merged_int_array = merged.Cast<int>().ToArray();
       
         foreach (int item in merged_int_array)
                 {
                   Console.Write(item);
                   Console.Write(" ");
                 }

      3) Финальный массив вообще не отсортируется – будут склены два отдельно отсортированных куска. выведется

      -45 -6 -1 0 3 5 8 13 22 55 -69 -55 -45 -41 3 5 13 40 522
      
  2. Игорь says:

    #include

    //слияние двух отсортированных массивов
    template
    void marge(T* arr1, int low1, int hight1,
    T* arr2, int low2, int hight2,
    T* arr3, int low3){
    int ndx1 = low1;
    int ndx2 = low2;
    int ndx3 = low3;
    while(ndx1 < = hight1 && ndx2 <= hight2){
    if(arr1[ndx1] < arr2[ndx2]) arr3[ndx3++] = arr1[ndx1++];
    else arr3[ndx3++] = arr2[ndx2++];
    }
    if(ndx1 > hight1) while(ndx2 <= hight2) arr3[ndx3++] = arr2[ndx2++];
    else while(ndx1 <= hight1) arr3[ndx3++] = arr1[ndx1++];
    }

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

  3. static void UniteMatrix(int[] arr1, int[] arr2)
            {
                int resLen = arr1.Length + arr2.Length;
                int[] result = new int[resLen];
                int pred = -100;
                int i = 0, p = 0, t = 1;
                while(i <= resLen)
                {
                    if (p < arr1.Length)
                    {
                        result[i] = arr1[p];
                        pred = arr1[p];
                    }
     
                    if (p < arr2.Length)
                    {
                        result[t] = arr2[p];
                        if (pred > arr2[p])
                        {
                            int temp = result[t];
                            result[t] = pred;
                            result[i] = temp;
                        }
                    }
                    p++; i += 2; t = i + 1;
                }
     
                foreach (var element in result)
                    Console.Write(element + " ");
            }

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

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


*