Projekt quicksort

[qwert1234]

Hej mam problem może mi ktoś pomóc . mam projekt do napisania .Program sortujący ciągi znakowe z pliku i losowe ciągi znakowe. Mam to zrobić przy pomocy quicksorta z medianą wielkości 1--15.

[PMichalak]

...i z czym masz problem?

[qwert1234]

Nie potrafię napisać sortowania dla ciągów znakowych i dokładnie nie wiem jak to będzie z tą medianą .
mam coś takiego :

Kod: Zaznacz cały

#include<unistd.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<stdint.h>


void quicksort1(int *, int, int);



void randomgen(int *, int);
void xchg(int *,int , int );

__inline__ uint64_t rdtsc()
{
   uint32_t lo, hi;
   __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
   return (uint64_t)hi << 32 | lo;
}

int main()
{
int *t;
int i,j,n,r,d;
clock_t time;
unsigned long long tics;
void (* tab[1])(int *, int, int)={quicksort1};
	
	
	printf("Podaj rozmiar tablicy: ");
	fflush(stdout);
	scanf("%d",&n);

	t=(int*)calloc(4,n);
	
	printf("
1 - losowo, 2 - odwrotnie, 3 - posortowane
");
	scanf("%d",&d);
	
	printf("
1 - Wersja bez mediany z trzech 2,3 - wersje z mediana
");	
for (j=0;j<1;j++)
{
	if (d==3)
		for(i=0;i<n;i++) t[i]=i;
	else if (d==2)
		for(i=0;i<n;i++) t[i]=n-i;
	else
		randomgen(t,n);

#ifdef TEST
	for(i=0;i<n;i++)
	printf("%d
",t[i]);
	printf("
");
#endif
	
	time=clock();
	tics=rdtsc();
	
	tab[j](t,0,n-1);
	
	tics=rdtsc()-tics;
	time=clock()-time;

#ifdef TEST
	for(i=0;i<n;i++)
	printf("%d
",t[i]);
#endif
	
	printf ("
Metoda nr %d 
",j+1);
	printf ("
Czas, funkcja clock:%.10f
",(double)( (time + 0.0) / CLOCKS_PER_SEC));
	printf ("Cykle procesora, rdtsc:%lld
", tics);
}

system("PAUSE");  //Windows
return 0;
}


void randomgen(int *t, int n)
{
int i;
srand(time(NULL));

	for(i=0;i<n;i++)
		t[i]= (int) ((double)n * (rand() / (RAND_MAX + 1.0)));
return;
}

		
	
void xchg(int *t,int i, int j)
{
int temp;

	temp=t[i];
	t[i]=t[j];
	t[j]=temp;
}
void quicksort1(int *t,int l,int r)
{
int temp,i,j;
//int i,j;
// Do bazowego algorytmu dodajemy podzial wg mediany z trzech
	
	if (r<=l) return;
//    xchg(t[(l+r)/2], t[r-1]); //przy losowych zbiorach niepotrzebne

	if(t[l]>t[r-1])	xchg(t,l,r-1); 
	if(t[l]>t[r])	xchg(t,l,r); 
	if(t[r-1]>t[r])	xchg(t,r,r-1); 

	if(r<=l+2) return; //jesli zbior ma mniej niz 4 elementy, to juz zostal posortowany
	
	i=l+1,j=r-2;temp=t[r-1];
	while(1)
	{
		for(;t[i]<temp;i++); //element nr r-1 jest pivotem	
		for(;t[j]>temp;j--);//mozemy wyeliminowac sprawdzanie prawego kranca
		if (i<j) xchg(t,i++,j--);
		else break;
	}
	xchg(t,i,r-1); 	quicksort1(t,i+1,r);	quicksort1(t,l,i-1);
}

[PMichalak]

2. Medianę mógłbyś szukać przy pomocy algorytmu magicznych piątek, ale tego się raczej nie stosuje w quicksorcie, chyba, że Twoj ćwiczeniowiec wymaga, żeby to była mediana, a nie 'prawie'-mediana. Można np. brać trzy losowe elementy i wybierać środkowy jako medianę.
3. Na charach/stringach jest określony porządek liniowy, możesz je porównywać używając < itp.
4. W praktyce opłaca się dla małych ciągów używać InsertionSorta, chociaż nei zmieni to złożoności.
5. Używaj znaczników

Kod: Zaznacz cały