sortari

[•toni2007]

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++)

[•StTwister]

sort din STL, usor de folosit, flexibil si garanteaza NlogN

Sau radix-sort, cand e nevoie, in functie de problema (foarte rar)

[•wefgef]

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.

[•toni2007]

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

[•wefgef]

Am impresia ca sortul din stdlib folosesti ca pivot elementul median .

Oricum, nu bate nimic sort-ul din STL .

[•toni2007]

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)

[•wefgef]

) Doar la ONI, IOI, BOI, CEOI, baraj, lot... Toate concursurile online si pe toate online judge-urile.

[•toni2007]

da... ai dreptate si la OJI presupun ca merge si qsortu ca n-o fi asa rau

[•wefgef]

Poate ca o sa fie si la OJI

[•toni2007]

cam asa arata implementat qsortul din stdlib

Cod:

#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 )?

[•bogdan2412]

interschimbi elementul din stanga cu unul de pe o pozitie random din sir. asa nu mai trebuie sa modifici restul functiei.

[•blue_phoenix]

QuickSort(implementat);e singurul algoritm eficient de sortare pe care il stiu

[•toni2007]

si te lauzi cu asta?

[•blasterz]

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

[•toni2007]

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

[•blasterz]

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 )

[•wefgef]

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?

[•blasterz]

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

[•wefgef]

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.

[•Binary_Fire]

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. 

[•chera_lary]

Folosesc HeapSort-ul si pana acum mi-a lasat impresia ca este cel mai rapid algoritm de sortare! Am lasat aici implementarea algoritmului :

Cod:

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

[•gabitzish1]

Eu am facut heapsort'ul cam asa:

Cod:

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

[•anna_bozianu]

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