Quicksort složitost

TomBar0

Newbie

25. 9. 2010 #1

Po dlouhé době zápasení a přepisování sem ze sebe vyprodukoval takovýto quicksort:

#include <iostream>

#include <ctime>



using namespace std;



void Swap(int& a,int& b){

     int temp;

     temp=a;

     a=b;

     b=a;}



void QuickSort(int array[],int left,int right)

    {

     int start=left;

     int end=right;

     int part;

     int pivot=(array[(left+right)/2]);

      cout<<left<<" "<<right<<endl;

      cin.get();

     while(right>left)

          {

         while(right>left)

              {

               if(array[right]>=pivot)right--;

               else break;

              }

         while(right>left)

              {

               if(array[left]<pivot)left++;

               else break;

              }

            cin.get();

    swap(array[left],array[right]);

      cout<<pivot<<endl;

      cout<<left<<" "<<right<<endl;

      cout<<array[right]<<" "<<array[left]<<endl;

     QuickSort(array,left+1,end);

     QuickSort(array,start,left);

     for(int n=0;n<10;n++)

        {

         cout<<array[n];}

         cout<<endl;

        }

    }

         

int main()

   {

    int nmb[10]={9,8,7,1,1,1,1,3,2,4};

//    int nmb[10]={1,5,2,6,7,3,2,1,2,3};

//    int nmb[10]={1,2,3,4,5,6,7,8,9,10};

//    int nmb[10];

//    srand((unsigned)time(0));

//    for(int a=0;a<10;a++){ 

//        nmb[a] = rand();

//        cout<<nmb[a]<<" ";}

    cout<<endl; 

    QuickSort(nmb,0,9);

      for(int n=0;n<10;n++)

         {

          cout<<nmb[n]<<" ";

         }   

    cin.get();

return 0;

   }

Jaká je prosím složitost tohoto algoritmu? Vím, že quicksort by měl být n*log(n), ale obávám se, že sem někde přidal podmínku navíc a nyní je to n*(log(n))^2. A ještě k tomu když to spočítám (možná to počítám špatně), tak mi to vyjde jako n^2 log(n)/2 + log(n)/2. Mohl by mi prosím někdo poradit jakou má toto tedy složitost a příp. jak se k tomu dospěje?

Děkuji

Nahlásit jako SPAM

IP: 217.229.52.–

Vitamin

~ Anonymní uživatel
~ 1092 příspěvků

25. 9. 2010 #2

V tom programe mas chybicku.
Pivot by mala byt stredna honota prvkov pola, ale zistit strenu hodnotu je narocne.
Preto ju treba dako tipnut. Lenze ak v tvojom programe tipnes za pivot akurat najmensiu honotu v poli tak sa pole neusporiada spravne.
Je to preto, lebo vzdy pridavas prvky rovne pivotu do pravej casti pola, tym paom ak je pivot najmensi prvok pola tak lava cast ostane prazdna.

skus si to pre napr. toto pole:

int nmb[10]={10,9,8,7,1,1,1,4,3,2};

vystup bude: 10 9 8 7 1 1 1 2 3 4

Dalej by bolo prehlanejsie pouzivat cykly while miesto for ked testujes len podmienku.
A ked je daco vnorene v cykle tak to aj odsait (vecsina editorov to urobi za teba).
A sprav si daky system pri zapisovani '{' '}', je to dost chaoticke :).

Nahlásit jako SPAM

IP: 95.105.128.–

TomBar0

Newbie

25. 9. 2010 #3

Teď jsem so pokusil pořešit ten pivot - napsal jsem

int pivot=(array[(left+right)/2]+1);

v tomhle případě mi to ale z nějakých záhadných důvodů nefunguje... prostě se to zapne a hned zase vypne (když to +1 smažu, tak to zase funguje). Dík za upozornění na tu chybu, vim že mi to předtím dělalo něco podobného s největším prvkej jako pivotem, na nejmenší jsem asi zapoměl.

Porád to ale bohužel neřeší můj hlavní problém - že složitost tohoto "quicksortu" je větší, než by měla být. Možná jí to řeší v tom smyslu, že pokud by nebyl pivot nejmenší člen, tak by tam nemuselo být to if (dal jsem ho tam myslím pro případ, že by pivot byl nejmenší prvek a right by se mi stále snižovalo).

Díky za odpověď

Nahlásit jako SPAM

IP: 217.229.52.–

Vitamin

~ Anonymní uživatel
~ 1092 příspěvků

26. 9. 2010 #4

Minuly rok som robil tieto triediace algoritmi do skoly. Tusim kazdy cyklus/rekruzia ktora prejde cez cele pole ja nasobok n. Rekruzivne volania v tomto pripade budu mat asi zlozitost log(n).

Nasiel som zadanie co som robil do skoly:



template <class DATA>    

DATA *quick_sort(DATA *data, unsigned len)

{

    DATA *a = data+1, *b=data+len-1, *med = data;

    unsigned a_len=0u, b_len=0u;



    if(len==1)return data;

    while( a <= b ){

        if(*a > *med){

            if(a != b)swap(*a, *b);

            b--;

            b_len++;

            }

        else {

            a++;

            a_len++;

            }

        }

    if(!a_len){

        a=data;

        a_len=1;

        b=data+1;

        }

    else if(!b_len){

        swap(data[len-1u], *med);

        

        a=data;

        b=data+len-1u;b_len=1u;

        }

    else{

        a = data;

        a_len++;

 

        b++;

        }    

    quick_sort(a, a_len);

    quick_sort(b, b_len);

    

    return NULL;

}