|
| sortowanie kubelkowe (cpp) |
|
|
Wysłano: Piątek, 21 Maj 2004, 19:11 |
|
|
|
witam!!
przepraszam,ze Was tak mecze.. ale teraz potrzbuje algorytm kubelkowy..
sama implementacja tego algorytmu
mam nadzieje,ze teraz sobie poradze z plikami :)
pozdrawiam! |
|
|
|
|
|
|
|
|
| Re: sortowanie kubelkowe (cpp) |
|
|
Wysłano: Środa, 26 Maj 2004, 00:42 |
|
|
|
witam ponownie,
mam nadzieje, ze nie za pozno.
w sortowaniu kubelkowym zakladasz ze liczby sa z przedzialu [0,1). Swoja droga kazdy zbior mozna tak przekszatalcic dzielac kazda przez najwieksza+1. Sortowanie jest wydajne (i do tego zostalo stworzone) gdy liczby dziela sie rownomiernie.
Tworzymy zaleznie od dzielnika n/dzielnik kubelkow (bedacych posortowana lista w mojej implementacji) i kazda liczbe do jednego z nich wkladamy.
Sortowanie listy (wkladanie w odpowiednie miejsce) jest bardzo szybkie bo lista ma srednio dzielnik elementow.
Potem z listy przenosimy do tablicy i zwalniamy pamiec. Duza zlozonosc pamieciowa - O(n), czasowa mala - O(n).
Kod: |
#include <stdio.h>
#include <stdlib.h>
#define dzielnik 3
typedef struct list{
float l;
struct list *next;
}LIST;
void kubel(float A[],int n){
int i,j,kubelkow=n/dzielnik;
LIST *K[kubelkow],*t1,*t2,*nowy;
for(i=0;i<kubelkow;i++)
K[i]=0;
for(i=0;i<n;i++){
nowy=malloc(sizeof(LIST));
nowy->l=A[i];
t1=K[(int)(A[i]*kubelkow)];
if(t1==0 || t1->l >= A[i]){
nowy->next=t1;
K[(int)(A[i]*kubelkow)]=nowy;
}
else{
while(t1->l < A[i]){
t2=t1;
if(!t1->next)
break;
t1=t1->next;
}
nowy->next=t2->next;
t2->next=nowy;
}
}
for(i=0,j=0;i<kubelkow;i++){
t1=K[i];
while(t1){
A[j]=t1->l;
t2=t1;
t1=t1->next;
free(t2);
j++;
}
}
}
void drukuj(float A[],int n){
int i;
for(i=0;i<n;i++)
printf("%.2f ",A[i]);
printf("\n");
}
int main(){
float A[1000];
int i,n=100;
for(i=0;i<n;i++)
A[i]=abs(((rand()+i)*rand()*i& #41;)%100/100.0; /*losujemy n liczb z przedzialu [0,1)*/
drukuj(A,n);
kubel(A,n);
drukuj(A,n);
getchar();
return 0;
} |
z wczytaniem z plikow mam nadzieje sobie poradzisz.
To jest pisane w ansi c, wiec sa dziwne 'malloc' zamiast 'new'. |
|
|
|
|
|
|
|
|
| Re: sortowanie kubelkowe (cpp) |
|
|
Wysłano: Środa, 26 Maj 2004, 17:12 |
|
|
|
|
|
|
|
|
| Re: sortowanie kubelkowe (cpp) |
|
|
Wysłano: Niedziela, 13 Czerwca 2004, 21:58 |
|
|
|
jeden z forumowiczow poprosil mnie o sprawdzenie czemu mu pod Borlandem nie dziala ten kod. No i sprawdzilem..
kretynski kompilator nie potrafi zaalokowac pamieci dla tablicy o zmiennej dlugosci przy wywolaniu funkcji
Kod: |
LIST *K[kubelkow],*t1,*t2,*nowy; |
przedstawiam zatem obejscie problemu:
c: |
#include <stdio.h>
#include <stdlib.h>
#define dzielnik 3
typedef struct list{
float l;
struct list *next;
}LIST;
void kubel(float A[],int n){
int i,j,kubelkow=n/dzielnik;
LIST **K,*t1,*t2,*nowy;
K=(LIST**)malloc(kubelkow*sizeof(LIST*));
for(i=0;i<kubelkow;i++)
K[i]=0;
for(i=0;i<n;i++){
nowy=(LIST*)malloc(sizeof(LIST));
nowy->l=A[i];
t1=K[(int)(A[i]*kubelkow)];
if(t1==0 || t1->l >= A[i]){
nowy->next=t1;
K[(int)(A[i]*kubelkow)]=nowy;
}
else{
while(t1->l < A[i]){
t2=t1;
if(!t1->next)
break;
t1=t1->next;
}
nowy->next=t2->next;
t2->next=nowy;
}
}
for(i=0,j=0;i<kubelkow;i++){
t1=K[i];
while(t1){
A[j]=t1->l;
t2=t1;
t1=t1->next;
free(t2);
j++;
}
}
free(K);
}
void drukuj(float A[],int n){
int i;
for(i=0;i<n;i++)
printf("%.2f ",A[i]);
printf("\n");
}
int main(){
float A[1000];
int i,n=100;
for(i=0;i<n;i++)
if((A[i]=abs(((rand()+i)*rand& #40;)*i))%100/100.0)<0)
A[i]=0.50;
drukuj(A,n);
kubel(A,n);
drukuj(A,n);
getchar();
return 0;
}
|
przy okazji testow z borlandem 3.11 pojawil sie kolejny dowcip autorstwa tej fajnej firmy.
Wg niego abs(-32768)=-32768... polecam sprawdzic..
stad to dziwne "if" przy losowaniu danych testowych. |
|
|
|
|
|