Сортировка слиянием в C с O (N * log [N]) Runtime - PullRequest
Новая
       12

Сортировка слиянием в C с O (N * log [N]) Runtime

1 голос
/ 14 апреля 2011

Для назначения мы должны написать функцию сортировки слиянием в C: 

sort(int* array, unsigned len);

У меня есть код, написанный и работающий, но его время выполнения равно O(N^2*log[N]), что противоречит цели сортировки слиянием. Причина неэффективности в том, что часть слияния выглядит следующим образом: 

while(ct1 < len1 && ct2 < len2){
    if(array[0] < array[len1 - ct1]){
        ct1++;
        array++;    // no longer look at that element
    }
    else{
        int position = len1 - ct1;
        int hold = array[position];
        while(position > 0){
            array[position] = array[position - 1];
            position--;
        }
        array[0] = hold;
        ct2++;
        array++;
    }
}

, где ct1 - счетчик для левого списка, ct2 - счетчик для правого списка, а массив - указатель на массив. И ct1, и ct2 изначально установлены на ноль. Как я уже сказал, это работает, это просто неэффективно, потому что вы должны все изменить. Я хотел разделить вложенные массивы на два временных массива перед сортировкой, но вы, вероятно, не можете создать массивы, длина которых не определена как константа. Следует также отметить, что хотя я могу использовать вспомогательные функции, я не могу изменить параметры функции: должен быть указатель на массив и его длину.

1 Ответ

2 голосов
/ 14 апреля 2011

Вы можете создавать массивы, которые не имеют постоянной длины, Google malloc. Сортировка слиянием требует использования вспомогательной памяти для правильной работы. Вы должны free памяти, выделенной malloc, когда вы закончите с этим.

...