Forum Dyskusyjne
Zaloguj Rejestracja Szukaj Forum dyskusyjne

Forum dyskusyjne -> Software -> Programowanie :: WWW -> sortowanie kubelkowe (cpp)
Napisz nowy temat  Odpowiedz do tematu
sortowanie kubelkowe (cpp)
PostWysłano: Piątek, 21 Maj 2004, 19:11 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




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)
PostWysłano: Środa, 26 Maj 2004, 00:42 Odpowiedz bez cytowania Odpowiedz z cytatem
Tassadar
Kapitan Heh
 
Użytkownik #3
Posty: 246


[ Osobista Galeria ]




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)
PostWysłano: Środa, 26 Maj 2004, 17:12 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




dzieki !

pozdrawiam!
  
Re: sortowanie kubelkowe (cpp)
PostWysłano: Niedziela, 13 Czerwca 2004, 21:58 Odpowiedz bez cytowania Odpowiedz z cytatem
Tassadar
Kapitan Heh
 
Użytkownik #3
Posty: 246


[ Osobista Galeria ]




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.
  
Re: sortowanie kubelkowe (cpp)
PostWysłano: Piątek, 06 Sierpnia 2004, 02:07 Odpowiedz bez cytowania Odpowiedz z cytatem
szopenhałer
Czytelnik
<tt>Czytelnik</tt>
 
Użytkownik #1370
Posty: 3


[ Osobista Galeria ]




Tassadar : Niedziela, 13 Czerwca 2004 21:58 :
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.

nie wiem moze sie skompromituje
ale wydaje mi sie ze jak to jest w reprezentacji uzupelnien do dwoch a pewnie to moze im tak wyjsc tzn generalnie inty sa z przedzialu od -32768 do 32767
i jak zrobisz abs z -32768 to moze jakies dziwadlo wyjsc
z tego co pamietam to w u2 jest tak pierwszy bit liczy sie za -2^16 a reszta juz normalnie.
  
Re: sortowanie kubelkowe (cpp)
PostWysłano: Poniedziałek, 09 Sierpnia 2004, 19:41 Odpowiedz bez cytowania Odpowiedz z cytatem
Tassadar
Kapitan Heh
 
Użytkownik #3
Posty: 246


[ Osobista Galeria ]




hmm, dosc ciekawy sposob liczenia u2. Ja znalem inny.

Zgadza sie. To jest jeden z problemow, o ktory trzeba zadbac np przy projektowaniu ukladow cyfrowych... ale nie moze byc tak, ze ten jeden przypadek zostawiamy jako graniczny i malo prawdopodobny.
Zaznaczam, ze ja nie wklepalem tam -32768.. taki sie po prostu wylosowal i przez to ze abs zle zadzialal wiele rzeczy sie sypalo. Gdyby dac long int problem bylby ten sam (przy losowaniu).
W gcc oczywiscie nie ma tego bledu.
  
sortowanie kubelkowe (cpp)
Forum dyskusyjne -> Software -> Programowanie :: WWW

Strona 1 z 1  
  
  
 Napisz nowy temat  Odpowiedz do tematu  
Kopiowanie i rozpowszechnianie materiałów w całości lub części jest niedozwolone. Wszelkie informacje zawarte w tym miejscu są chronione prawem autorskim.



Forum dyskusyjne Heh.pl © 2002-2010