Сортировка по основанию вектора целых чисел с использованием вектора векторов целых чисел

Недавно я попытался реализовать сортировку по основанию для вектора пары целых чисел (где второй элемент рассматривается только тогда, когда первые элементы равны). Я сделал это, дважды применив сортировку подсчетом — сначала ко второму элементу пары, а затем к первому элементу. Вот как я сначала реализовал сортировку подсчетом:

//vector to be sorted (of size n).
vector<int> arr;

//arr gets filled here


//N-1 is the maximum number which can occur in the array. N was equal to n in my case
vector<vector<int> > mat(N);

for (int i=0;i<n;i++)
{
    mat[arr[i]].push_back(i);
}

//array in which the sorted array will be stored
vector<int> arr2;

for (int i=0;i<N;i++)
{
    for(int j=0;j<sz(mat[i]);j++) arr2.push_back(arr1[mat[i][j]]);
}

Очевидно, что первый цикл for выполняется за O(n). Поскольку массив «mat» содержит ровно n элементов, доступ к нему будет осуществляться не более 2n раз во втором (вложенном) цикле. Это означает, что приведенный выше код имеет временную сложность O(n), как и должно быть.

Затем я сравнил время выполнения этого кода с STL sort() (который имеет временную сложность O(nlog(n))), запустив оба из них на массиве из 10 ^ 6 элементов. К моему большому удивлению, STL sort() оказалась немного лучше, чем моя реализация поразрядной сортировки.

Затем я изменил свою реализацию сортировки подсчета на следующую:

//vector to be sorted (of size n).
vector<int> arr;

//arr gets filled here

//N-1 is the maximum number which can occur in the array. N was equal to n in my case
vector<int> temp(N,0);

for(int i=0;i<n;i++) temp[arr[i]]++;

for(int i=1;i<N;i++) temp[i]+=temp[i-1];

//array in which the sorted array will be stored
vector<int> arr2(n);

for(int i=n-1;i>=0;i--) arr2[--temp[arr[i]]]=arr[i];

На этот раз поразрядная сортировка работала примерно в 5-6 раз быстрее, чем STL sort(). Это наблюдение заставило меня задуматься, почему моя первая реализация поразрядной сортировки работает намного медленнее, чем вторая, когда обе они равны O(n)?


c++ radix-sort
person Shubham    schedule 16.08.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы используете псевдо алгоритм. Его сложность O(M), где

M = std::max_element(arr.begin(), arr.end())

Вы не можете сравнить это с std::sort, сложность которого O(N log(N)), где

N = arr.size()

Вторая версия выделяет temp один раз, в то время как вызовы push_back в первой версии могут привести к множеству выделений, влияющих на производительность.

Поразрядная сортировка — это другой алгоритм. Проверьте эту ссылку.

person a.lasram    schedule 16.08.2013
comment
Прежде всего, вместо того, чтобы применять сортировку по основанию для сортировки массива чисел по одной цифре за раз, здесь я использую ее для сортировки массива пар целых чисел, используя те же основные принципы. Во-вторых, как я уже упоминал в комментариях к фрагментам кода в моем вопросе, в моем случае M = N-1. Что касается вызовов push_back, вызывающих замедление, это может иметь место, хотя, учитывая степень, в которой они влияют на производительность (разница в 10 секунд на моей машине i5-3230 при запуске с миллионом элементов), я бы подумал, что немного маловероятно. - person Shubham; 17.08.2013
comment
Например, программа, которая вводит миллион элементов в вектор заранее заданного размера, работает всего на несколько миллисекунд быстрее, чем та, которая вместо этого вставляет в него миллион элементов (по крайней мере, на моей машине). - person Shubham; 17.08.2013