sortowanie babelkowe

Question

Cześć mam pytanie dotyczące udoskonalenia sortowania bąbelkowego. Słyszałem, że jest możliwość zaimplementowania równoległego sortowania tylko nie do końca wiem jak to zrobić. Może mi ktoś wytłumaczyć na czym to polega? Ogólnie to szukam sposobu na zmniejszenie ilości zamian. Tutaj podsyłam dwa algorytmy i jak można wycisnąć coś więcej z nich :) 

unsigned long long bubble3(double *d,unsigned long long N)
{
    unsigned long long swaps=0;
    int i,p,pmin,pmax;
    pmin = 0;
    pmax = N - 1;
    pmin = 0;
    pmax = N - 2;
    do
    {
        p = -1;
        for(i = pmin; i <= pmax; i++)
            if(d[i] > d[i + 1])
            {
                swap(d[i], d[i + 1]);
                p = i;
                swaps++;
            }
        if(p < 0)
            break;
        pmax = p - 1;
        p = -1;
        for(i = pmax; i >= pmin; i--)
            if(d[i] > d[i + 1])
            {
                swap(d[i], d[i + 1]);
                p = i;
                swaps++;
            }
        pmin = p + 1;
    }
    while(p >= 0);

    return swaps;
}






unsigned long long bubbleSortPerf(double *t,unsigned long long N)
{
    int zamiana=1,k=0;
    unsigned long long licznik=0;
    double schowek;

    do
    {

        zamiana=0;
        for (int i=k; i<N-1-k; i++)
        {
            if (t[i]>t[i+1])
            {
                zamiana++;
                schowek=t[i];
                t[i]=t[i+1];
                t[i+1]=schowek;
                licznik++;
            }

        }
        zamiana=0;
        for(int j=N-2-k; j>k; j--)
        {
            if (t[j]<t[j-1])
            {
                zamiana++;
                schowek=t[j];
                t[j]=t[j-1];
                t[j-1]=schowek;
                licznik++;
            }
        }
        k++;
    }
    while(zamiana!=0);

    return licznik;
}

 

Comments

Popraw formatowanie, bo nie wiadomo co do czego...

---

Proszę

Answer 1

Tu jest pseudokod wielowątkowego bubble sorta. Niestety nie znam się na wątkach w C++, więc mogę tylko podlinkować:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bubbleSort.htm

Comments

Myślisz, że to pomoże zredukować ilość zamian liczb?

---

zamian będzie tyle samo, ale będą się robić równolegle więc algorytm zadziała szybciej

---

Napisałem taki kod ale nie jestem pewny czy o to chodziło.

unsigned long long bubbleparallel(double*t,unsigned long long N)
{
    int i,zamiana;
    double temp;
    unsigned long long swaps=0;

    for(int k=0;k<N-2;k++)
    {

        zamiana=0;

        for(i=0;i<(N/2);i++)
        if(t[2*i]>t[2*i+1]){
            swap(t[2*i],t[2*i+1]);
            zamiana++;
            swaps++;
        }
        for(i=0;i<(N/2)-1;i++)
        {
            if(t[2*i+1]>t[2*i+2])
            {
                swap(t[2*i+1],t[2*i+2]);
                zamiana++;
                swaps++;
            }
        }

    }

    return swaps;
}

 

---

Nic tutaj nie dzieje się równolegle. 

Słyszałem, że jest możliwość zaimplementowania równoległego sortowania tylko nie do końca wiem jak to zrobić.

Trzeba zrobić to wielowątkowo, tylko tak jak pisałem sam nie znam się na wielowątkowości w C++. Wielowątkowość działa tak, że masz kilka kontekstów wykonywanego programu. W tym momencie "interpreter" programu idzie linijka po linijce i nigdy nie pójdzie do kolejnej jeśli nie skończy obecnej. Można to rozwiązać wprowadzeniem kolejnego wątku, wtedy dwie linijki mogą się wykonywać jednocześnie. Jeśli bardzo nie rozumiesz idei to możesz o tym myśleć tak, że są dwa programy z tym samym kodem, które wykonują się oddzielnie tyle, że pracują na tych samych danych np na tej samej tablicy.