Quicksort složitost – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Quicksort složitost – C / C++ – Fórum – Programujte.comQuicksort složitost – C / C++ – Fórum – Programujte.com

 

TomBar0
Newbie
25. 9. 2010   #1
-
0
-

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
-
0
-

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
-
0
-

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
-
0
-

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;
}

V mojom programe mas len 1 cyklus a potom uz len rekruzivne volania. Cize to bue asi to O = n*log(n)

Nahlásit jako SPAM
IP: 95.105.128.–
zdenda
~ Anonymní uživatel
257 příspěvků
26. 9. 2010   #5
-
0
-

Doufám, že ty listingy jsou jen zmršené zdejším systémem.

Nahlásit jako SPAM
IP: 213.211.51.–
TomBar0
Newbie
28. 9. 2010   #6
-
0
-

Díky za odpovědi, už jsem to rozchodil a závorky si taky opravil (nebylo to systémem :-) )

Nahlásit jako SPAM
IP: 217.229.29.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 102 hostů

Podobná vlákna

Quicksort v assembleru — založil myšák

QuickSort padá — založil unik

Podkopávání algoritmu Quicksort — založil Petr Zakopal

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý