•toni2007
|
|
« : Aprilie 05, 2008, 21:26:47 » |
|
voi ce sortari folositi?
si eventual argumentati
eu pana la un moment dat foloseam qsortul din stdlib.h pentru ca era usor de implementat, dar de curand am trecut la heapsort pentru ca are intotdeauna N lg N (lucrez in c deci nu folosesc algorithm si sort care e pt c++)
|
|
« Ultima modificare: Aprilie 05, 2008, 21:50:25 de către Pripoae Teodor Anton »
|
Memorat
|
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #1 : Aprilie 05, 2008, 21:45:04 » |
|
sort din STL, usor de folosit, flexibil si garanteaza NlogN
Sau radix-sort, cand e nevoie, in functie de problema (foarte rar)
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #2 : Aprilie 05, 2008, 23:46:27 » |
|
Folositi qsort (randomizat daca il faceti de mana) cu incredere. Sansele sa va mearga mai prost decat heapsort sunt mai mici decat sa castigati la loto.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•toni2007
|
|
« Răspunde #3 : Aprilie 06, 2008, 08:48:44 » |
|
Folositi qsort (randomizat daca il faceti de mana) cu incredere. Sansele sa va mearga mai prost decat heapsort sunt mai mici decat sa castigati la loto.
eu stiam ca qsortul din stdlib este implementarea exacta a quicksortului, dar abia acum am vazut ca e cam depasit, adica de multe ori merge mai incet decat heap-u (am refacut intr-o seara "reactivi" si "submat" doar schimband sortarea si mergea ceva mai repede si concuma ceva mai putina memorie (80% din cat concuma qsortul) si la pb "orase" heap-ul avea pe cel mai mare test 80 de ms pe cand qsortu si iesea cu 204 ms pe un test
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #4 : Aprilie 06, 2008, 08:52:04 » |
|
Am impresia ca sortul din stdlib folosesti ca pivot elementul median . Oricum, nu bate nimic sort-ul din STL .
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•toni2007
|
|
« Răspunde #5 : Aprilie 06, 2008, 08:53:47 » |
|
poi da... sortul din STL e un hibrid intre quicksort si heapsort (care daca se intampla nuj ce trece de pe quicksort pe heapsort) dar faza e ca STL-ul nu il ai la toate concursurile (doar la ONI)
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #6 : Aprilie 06, 2008, 08:58:17 » |
|
) Doar la ONI, IOI, BOI, CEOI, baraj, lot... Toate concursurile online si pe toate online judge-urile.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•toni2007
|
|
« Răspunde #7 : Aprilie 06, 2008, 09:00:40 » |
|
da... ai dreptate si la OJI presupun ca merge si qsortu ca n-o fi asa rau
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #8 : Aprilie 06, 2008, 09:04:21 » |
|
Poate ca o sa fie si la OJI
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•toni2007
|
|
« Răspunde #9 : Aprilie 06, 2008, 09:05:47 » |
|
cam asa arata implementat qsortul din stdlib #include <stdlib.h> #include <memory.h>
void _RTL_FUNC quicksort(const void *base, int lo, int hi, size_t width, int (*compare)(const void *elem1, const void *elem2), char *buf) {
if (hi > lo) { int i=lo, j=hi; char * celem = buf + width; memcpy(celem,((char *)base) + width * ((lo + hi) / 2),width) ;
while (i <= j) { while (i <= hi && (*compare)((char *)base + i * width, celem) <0) i++; while (j >= lo && (*compare)((char *)base + j * width, celem) >0) j--; if (i<=j) { memcpy(buf, (char *)base + i * width, width) ; memcpy((char *)base + i * width, (char *)base + j * width, width) ; memcpy((char *)base + j * width, buf, width) ; i++; j--; } } if (lo<j) quicksort(base, lo, j,width,compare,buf); if (i<hi) quicksort(base, i, hi,width,compare,buf); }
} void _RTL_FUNC qsort(const void *base, size_t num, size_t width, int (*compare)(const void *elem1, const void *elem2)) { char data[512]; char *buf ;
if (width <= sizeof(data)/2) buf = data; else { buf = malloc(width) ; if (!buf) return ; } quicksort(base,0,num-1,width, compare,buf) ;
if (buf != data) free(buf) ; }
cam cum ar arata un quicksort cu pivot random (dau pivot=rand()%n )?
|
|
« Ultima modificare: Aprilie 07, 2008, 21:21:45 de către Pripoae Teodor Anton »
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #10 : Aprilie 08, 2008, 11:48:25 » |
|
interschimbi elementul din stanga cu unul de pe o pozitie random din sir. asa nu mai trebuie sa modifici restul functiei.
|
|
|
Memorat
|
|
|
|
•blue_phoenix
Client obisnuit
Karma: 0
Deconectat
Mesaje: 57
|
|
« Răspunde #11 : Aprilie 24, 2008, 20:15:34 » |
|
QuickSort(implementat);e singurul algoritm eficient de sortare pe care il stiu
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #12 : Aprilie 24, 2008, 20:52:02 » |
|
si te lauzi cu asta?
|
|
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #13 : Aprilie 24, 2008, 20:55:51 » |
|
Am impresia ca sortul din stdlib folosesti ca pivot elementul median . Oricum, nu bate nimic sort-ul din STL . Il bate radix implementat pe cate 10 biti deodata (testat) Pe computerul meu sort din stl ruleaza pt n=1000 000 in 0,255 secunde iar radix in 0,08
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #14 : Aprilie 24, 2008, 21:18:39 » |
|
pai depinde eu pe un array de 1 000 000 de elemente cu maximul 1 000 000 am scos asa: qsort | 1.54 | sort | 1.23 | heapsort | 1.67 | bucketsort | 0.97 | shell | 1.45 |
|
|
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #15 : Aprilie 24, 2008, 21:21:56 » |
|
pai depinde eu pe un array de 1 000 000 de elemente cu maximul 1 000 000 am scos asa: qsort | 1.54 | sort | 1.23 | heapsort | 1.67 | bucketsort | 0.97 | shell | 1.45 |
Eu am scos 0,08 pt elemente <= 2^32 )
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #16 : Aprilie 24, 2008, 21:22:43 » |
|
Aici e vorba de sortari, nu de sortari de numere intregi (cu toate ca apare la voturi).
Merge intr-adevar mai bine radixul... dar la ce folos?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•blasterz
|
|
« Răspunde #17 : Aprilie 24, 2008, 21:25:40 » |
|
Pai de exemplu la suffix array (varianta O(nlogn))... cand ai de facut n sortari... merge mai repede decat O(nlog^2n)...de cel putin 2 ori mai repede
Si de ce spui ca merge doar pentru numere intregi? daca ai numere reale inmultesti cu 10^9 ...
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #18 : Aprilie 24, 2008, 21:31:35 » |
|
Eu ziceam ca aplicabilitatea radix sort-ului este restransa. In general cand sortezi nu ai numere intregi. In afara de suff array nu cred ca am intalnit prea multe locuri in care sa fie necesar radix.
Din aceasta cauza ziceam ca radix-ul e bun.. dar degeaba.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Binary_Fire
Client obisnuit
Karma: 82
Deconectat
Mesaje: 87
|
|
« Răspunde #19 : Aprilie 24, 2008, 21:34:49 » |
|
Eu din cate vad va referiti doar in aria concursurilor de informatica, dar o aplicatie in programarea reala a radix-sortului este in grafica calculatoarelor, acolo chiar este uneori nevoie de sortari cat se poate de rapide.
|
|
|
Memorat
|
|
|
|
•chera_lary
|
|
« Răspunde #20 : August 16, 2008, 15:47:55 » |
|
Folosesc HeapSort-ul si pana acum mi-a lasat impresia ca este cel mai rapid algoritm de sortare! Am lasat aici implementarea algoritmului : #include <stdio.h> #include <conio.h>
void heapsort(int[],int);
void main(){ clrscr(); int i; int a[]={1,56,23,52,47,79,12,97}; for(i=sizeof(a)/sizeof(*a);i>1;i--) heapsort(a,i-1); for(i=0;i<sizeof(a)/sizeof(*a);i++) printf("%4d",a[i]); getch(); }
void heapsort(int a[],int limita_a){ int i,o; int fiu_stanga,fiu_dreapta,fiu_mijloc,radacina,temp; radacina=(limita_a-1)/2; for(o=radacina;o>=0;o--){ for(i=radacina;i>=0;i--){ fiu_stanga=2*i+1; fiu_dreapta=2*i+2; if((fiu_stanga<=limita_a)&&(fiu_dreapta<=limita_a)){ if(a[fiu_dreapta]>a[fiu_stanga]) fiu_mijloc=fiu_dreapta; else fiu_mijloc=fiu_stanga; }else{ if(fiu_dreapta>limita_a) fiu_mijloc=fiu_stanga; else fiu_mijloc=fiu_dreapta; } if(a[i]<a[fiu_mijloc]){ temp=a[i]; a[i]=a[fiu_mijloc]; a[fiu_mijloc]=temp; } } } temp=a[0]; a[0]=a[limita_a]; a[limita_a]=temp; return; }
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #21 : August 16, 2008, 18:03:02 » |
|
Eu am facut heapsort'ul cam asa: //Heapsort #include <stdio.h>
int n, v[1000];
void swap(int x, int y) { int aux; aux = v[x]; v[x] = v[y]; v[y] = aux; }
void urc(int k) { if (v[k] > v[(k-1)/2]) { swap(k, (k-1)/2); urc((k-1)/2); } }
void cobor(int k) { int s, d, max; s = 2*k+1; d = 2*k+2;
if (s < n && v[s] > v[k]) max = s; else max = k;
if (d < n && v[d] > v[max]) max = d;
if (max != k) { swap(k,max); cobor(max); } }
int main() { freopen("heapsort.in","r",stdin); freopen("heapsort.out","w",stdout);
int i;
scanf("%d",&n); for (i = 0; i < n; i++) scanf("%d", v+i);
for (i = n - 1; i > 0; i--) urc(i);
while (n > 1) { swap(0,n-1); n--; cobor(0); }
for (i = 0; i < n; i++) printf("%d ",v[i]); return 0; }
|
|
|
Memorat
|
|
|
|
•anna_bozianu
|
|
« Răspunde #22 : August 16, 2008, 20:28:19 » |
|
Alta varianta de implementare heap-sort ... int i,n,x[N]; ... void swap(int i1,int i2) { int aux=x[i1]; x[i1]=x[i2]; x[i2]=aux; } void heapdown(int ic, int nc) { int is=ic<<1; if(is>nc)return; if(is<nc) if(x[is+1]>x[is])is++; if(x[is]>x[ic]){ swap(is,ic); hd(is,nc); } } int main() { .... for( i=n/2; i>=1; i-- ) heapdown(i,n); for( i=n; i>=1; i--) { swap(1,i); heapdown(1,i-1); } ... return 0; }
|
|
|
Memorat
|
|
|
|
|