Projekt quicksort
Projekt quicksort
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.
Projekt quicksort
Nie potrafię napisać sortowania dla ciągów znakowych i dokładnie nie wiem jak to będzie z tą medianą .
mam coś takiego :
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);
}
-
- Użytkownik
- Posty: 125
- Rejestracja: 29 paź 2009, o 20:03
- Płeć: Mężczyzna
- Lokalizacja: Kalisz
- Podziękował: 1 raz
- Pomógł: 16 razy
Projekt quicksort
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
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