Почему мой алгоритм рекурсивной быстрой сортировки имеет такие односторонние разделы?

Question

Я реализовал алгоритм быстрой сортировки в C ++. Однако мой алгоритм работает намного медленнее, чем мой алгоритм сортировки слиянием. Он работает намного быстрее на обращенных массивах, но в противном случае это занимает в четыре или пять раз больше времени.

Мой алгоритм использует рекурсию, хотя я не думаю, что это проблема. Я попытался переключиться на случайную опорную точку вместо медианы выбора из трех опорных точек. Это было еще медленнее.

Включает в себя:

#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<iostream>

unsigned int recurse(int*a,unsigned int length)
{
    int value=0;
    unsigned int depth=0;
    if(length<=1)
    {
        depth=1;
    }
    else if(length==2)
    {
        if(a[0]>a[1])
        {
            value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
        depth=1;
    }
    else if(length==3)
    {
        if(a[0]>a[1])
        {
            value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
        if(a[0]>a[2])
        {
            value=a[0];
            a[0]=a[2];
            a[2]=value;
        }
        if(a[1]>a[2])
        {
            value=a[1];
            a[1]=a[2];
            a[2]=value;
        }
        depth=1;
    }
    else
    {
        //unsigned int fifth=(length>>3)+(length>>4)+(length>>6);
        unsigned int middle=length>>1;
        unsigned int choices[5]={0,middle>>1,middle,middle+(middle>>1),length-1};
        unsigned int left=0;
        unsigned int right=length-1;
        unsigned int index=0;
        for(unsigned int i=0;i<4;i++)
        {
            index=i;
            while(a[choices[index]]>a[choices[index+1]])
            {
                value=a[choices[index]];
                a[choices[index]]=a[choices[index+1]];
                a[choices[index+1]]=value;
                if(index>0)
                {
                    index--;
                }
            }
        }
        while(right>left)
        {
            while((a[++left]<=a[middle])&&right>left);
            while((a[--right]>=a[middle])&&right>left);
            if(right>left)
            {
                value=a[left];
                a[left]=a[right];
                a[right]=value;
            }
        }
        value=a[middle];
        if(left<middle&&right<middle)
        {
            a[middle]=a[left];
            a[left]=value;
            middle=left;
        }
        else if(left>middle&&right>middle)
        {
            a[middle]=a[left-1];
            a[left-1]=value;
            middle=left-1;
        }
        long double y;
        x++;
        ratio+=y=fabs((long double)(length>>1)-(long double)middle)/length;
        if(length>=1048576)
        {
            cout<<middle<<" "<<length<<" "<<y<<endl;
        }
        depth=max(recurse(a,middle),recurse(a+middle+1,length-middle-1))+1;
    }
    return depth;
}

Глубина была только для подсчета глубины рекурсии. Я пытался понять, была ли это проблема.

int main(int argl,char**argv)
{
    unsigned int length=0;
    cin>>length;
    cout<<length<<endl;
    int*numbers=new int[length];
    for(unsigned int i=0;i<length;i++)
    {
        numbers[i]=(int)rand()%(length<<1);
    }
    time_t start=time(0);
    mergesort(numbers,length);
    time_t end=time(0);
    cout<<end-start<<endl;
    for(unsigned int i=0;i<length;i++)
    {
        numbers[i]=(int)rand()%(length<<1);
    }
    start=time(0);
    unsigned int depth=recurse(numbers,length);
    end=time(0);
    cout<<end-start<<endl;
    cout<<"Depth: "<<depth<<endl;
    return 0;
}

Редактировать: код для сортировки слиянием, согласно запросу:

void mergesort(int*a,unsigned int length)
{
    if(length<=1)
    {
        return;
    }
    else if(length==2)
    {
        if(a[0]>a[1])
        {
            int value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
    }
    else
    {
        unsigned int index1=0,index2=0;
        unsigned int divide1=1,divide2=1;
        unsigned int merge=2;
        unsigned int start=0;
        int*b=new int[length];
        while(merge<=length)
        {
            while(index1<divide1&&index2<divide2)
            {
                if(a[start+index1]>a[start+divide1+index2])
                {
                    b[start+index1+index2]=a[start+divide1+index2++];
                }
                else
                {
                    b[start+index1+index2]=a[start+index1++];
                }
            }
            if(index1<divide1)
            {
                for(unsigned int i=index1;index1<divide1;index1++)
                {
                    b[start+index1+index2]=a[start+index1];
                }
            }
            else
            {
                for(unsigned int i=index2;index2<divide2;index2++)
                {
                    b[start+index1+index2]=a[start+divide1+index2];
                }
            }
            if(start+merge>=length)
            {
                if(start==0)
                {
                    merge<<=1;
                }
                else
                {
                    start=0;
                    index1=0;
                    index2=0;
                    divide1=merge;
                    divide2=merge<<1>length?length-divide1:merge;
                    merge=divide1+divide2;
                }
                for(unsigned int i=0;i<length;i++)
                {
                    a[i]=b[i];
                }
            }
            else
            {
                start+=merge;
                index1=0;
                index2=0;
                divide1=start+divide1>length?length-start:divide1;
                divide2=start+merge>length?max((int)(length-(start+divide1)),0):divide2;
            }
        }
    }
}

Результаты, для 33554432 номеров: Изменить, изменил мой код, обновил результаты:

33554432
33554432
8
22
Depth: 765
0.4437349830864823

Последнее число - это среднее расстояние, на которое разворачивается центр от середины. Это почти 0,45, почти от одного до двадцати.

Answer 1

Нет другого способа сделать это, кроме как ответить здесь.Если вы собираетесь позвонить new, сделайте соответствующий вызов delete.

rand() не так уж случайно, рассмотрите возможность использования случайной библиотеки C ++ 11.

Для краткости я не включил ваш алгоритм, но я не вносил в него никаких изменений.Я запустил этот код как в Ubuntu, так и в MacOS.

int main() {
    // Here are 50 random numbers I get when I use your method, I have put
    // them in a vector.
    std::vector<int> v = {7, 49, 89, 74, 34, 8, 24, 62, 35, 13, 24, 53,12,
                    2, 51, 71, 55, 49, 88, 52, 15, 49, 45, 5, 88, 21,
                    75, 54, 8, 7, 25, 50, 8, 19, 2, 33, 19, 13, 3, 69,
                    31, 80, 49, 72, 77, 65, 44, 43};

    // I set the size of the vector to be the size of this raw array.
    unsigned int length = v.size();

    int* numbers= new int[length];

    for(int i = 0; i < length; i++)
        numbers[i] = v[i];

    // 7 49 89 74 34 8 24 62 35 13 24 53 12 2 51 71 55...
    for (int i = 0; i < length; i++)
        std::cout << numbers[i] << " ";
    std::cout << std::endl;

    unsigned int depth = recurse(numbers, length);

    // 5 2 3 2 7 7 8 12 8 13 8 13 15 19 19 24...
    for (int i = 0; i < length; i++)
        std::cout << numbers[i] << " ";

    delete[] numbers;
    return 0;
}

Мне очень интересно, что здесь происходит.Может быть, я как-то ошибаюсь, но в любом случае надеюсь, что это поможет (по крайней мере, одному из нас).

Что касается причины, по которой мой ответ может иметь значение, так это то, что когда я запускаю ваш алгоритм слияния, он обнуляет все вмассив за исключением последнего элемента в массиве.Если это действительно так, возможно, кто-то другой может это подтвердить, то, вероятно, он делает это более эффективно, чем сортирует ваша быстрая сортировка.

Best,