Возникли проблемы с получением сортировки слиянием O (n log n)

В общем, я студент и у меня проблемы с сортировкой слиянием. Очевидно, что цель состоит в том, чтобы иметь O (n log n), но это больше n ^ 2. Я думаю, что проблема заключается в tempList, как вы увидите в коде, но в описании программы говорится, что нужно использовать static int tempList [LIST_SIZE], чтобы избежать ухудшения качества.

Вот что у меня есть, и время выполнения с использованием start составляет около 16000, что, очевидно, слишком долго для сортировки слияния.

    void mergeSort(int randomNum[], int lowIdx, int highIdx)
    {
        int midIdx;

        if (lowIdx < highIdx)
        {
            midIdx = (highIdx + lowIdx) / 2;
            mergeSort(randomNum, lowIdx, midIdx);
            mergeSort(randomNum, midIdx + 1, highIdx);
            merge(randomNum, lowIdx, midIdx, highIdx);
        }
    }

Вот вторая порция сортировки

    void merge(int randomNum[], int lowIdx, int midIdx, int highIdx)
    {
        static int tempList[MAX_SORT];

        for (int count = 0; count <= highIdx; count++)
            tempList[count] = randomNum[count];

        int leftIdx = lowIdx,
        rightIdx = midIdx + 1,
        tempPos = lowIdx;

        while (leftIdx <= midIdx && (rightIdx <= highIdx))
        {
            if (tempList[leftIdx] <= tempList[rightIdx])
            {
                randomNum[tempPos] = tempList[leftIdx];
                leftIdx++;
            }
            else
            {
                randomNum[tempPos] = tempList[rightIdx];
                rightIdx++;
            }
        tempPos++;
        }

        while (leftIdx <= midIdx)
        {
            randomNum[tempPos] = tempList[leftIdx];
            tempPos++;
            leftIdx++;
        }

        while (rightIdx <= highIdx)
        {
            randomNum[tempPos] = tempList[rightIdx];
            tempPos++;
            rightIdx++;
        }
    }

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

Может кто-нибудь помочь?


c++ arrays sorting mergesort
person user2649644    schedule 02.10.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Не уверен, что это все ваши проблемы, но это одна проблема:

Вы копируете randomNum в tempList из 0 в highIdx, но когда-либо получаете доступ только к tempList с lowIdx по highIdx.

Это означает, что все элементы, которые вы скопировали с 0 на lowIdx, являются потраченными впустую копиями.

Решение: копируйте только то, что вам нужно.

for (int count = lowIdx; count <= highIdx; count++)
person The Dark    schedule 02.10.2014
comment
Большое спасибо. Я знал, что у меня правильный код, за исключением того, что связано с tempList, но не был уверен, что было не так. Это полностью исправило это. - person user2649644; 02.10.2014

arrow_upward
0
arrow_downward

Возможно, вы захотите рассмотреть сортировку слиянием снизу вверх. Пример кода шаблона. a [] - это массив для сортировки, b [] - временный массив того же размера, что и a []. Отсортированные данные могут оказаться в a [] или b []. Это можно изменить, чтобы данные всегда заканчивались в [], выполнив проверку количества проходов в начале и, возможно, пропустив замену на месте, если будет четное количество проходов.

template <typename T>
T * BottomUpMergeSort(T a[], T b[], size_t n)
{
    for(size_t s = 1; s < n; s += 2)        // swap in place for 1st pass
        if(a[s] < a[s-1])
            std::swap(a[s], a[s-1]);
    for(size_t s = 2; s < n; s <<= 1){      // s = run size
        size_t ee = 0;                      // init end index
        while(ee < n){                      // merge pairs of runs
            size_t ll = ee;                 // ll = start of left  run
            size_t rr = ll+s;               // rr = start of right run
            if(rr >= n){                    // if only left run
                rr = n;
                BottomUpCopy(a, b, ll, rr); //   copy left run
                break;                      //   end of pass
            }
            ee = rr+s;                      // ee = end of right run
            if(ee > n)
                ee = n;
            BottomUpMerge(a, b, ll, rr, ee);
        }
        std::swap(a, b);                    // swap a and b
    }
    return a;                               // return sorted array
}

template <typename T>
void BottomUpCopy(T a[], T b[], size_t ll, size_t rr)
{
    while(ll < rr){                         // copy left run
        b[ll] = a[ll];
        ll++;
    }
}

template <typename T>
void BottomUpMerge(T a[], T b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                          // b[]       index
    size_t l = ll;                          // a[] left  index
    size_t r = rr;                          // a[] right index

    while(1){                               // merge data
        if(a[l] <= a[r]){                   // if a[l] <= a[r]
            b[o++] = a[l++];                //   copy a[l]
            if(l < rr)                      //   if not end of left run
                continue;                   //     continue (back to while)
            while(r < ee){                  //   else copy rest of right run
                b[o++] = a[r++];
            }
            break;                          //     and return
        } else {                            // else a[l] > a[r]
            b[o++] = a[r++];                //   copy a[r]
            if(r < ee)                      //   if not end of right run
                continue;                   //     continue (back to while)
            while(l < rr){                  //   else copy rest of left run
                b[o++] = a[l++];
            }
            break;                          //     and return
        }
    }
}
person rcgldr    schedule 02.10.2014