Forum Dyskusyjne
Zaloguj Rejestracja Szukaj Forum dyskusyjne

Forum dyskusyjne -> Software -> Programowanie :: WWW -> sortowanie liniowe - znow problem :( (c++)
Napisz nowy temat  Odpowiedz do tematu
sortowanie liniowe - znow problem :( (c++)
PostWysłano: Sobota, 15 Maj 2004, 09:50 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




heyka!!!

znowu mam problem z algorytmem tym razem sortowanie liniowe.Tresc brzmi tak samo jak ostatnio: zaimplementuj algorytm )alg. przez zliczanie)w jezyku c/c++. Implementacja powinna umozliwiac wczytywanie danych- l.typu calkowitego - z pliku oraz zapisywanie wynikow dzialania do pliku.
Hm nawet nie wiem do ktorej tablicy maja byc zapisywane wyniki dzialania..?? Napisalam cos takiego :

Kod:


#include <stdio.h>


void sort (void)  //tu chyba powinien cos zwracac tlyko ne wiem czy ma
                       //byc to int *tabA, int*tabB, int *tabC ??
                       
{
int z,i,size;
int tabA[size-1];
int tabB[size-1];
int tabC[z];
//szukanie najw. elem.
z=0;

for (i=0; i<size; i++)
  if (tabA[i]>z)
  z = tabA[i];

  //algorytm sort liniowego

  for (i=0; i < z+1; i++)
  tabC[i] = 0;
  for (i=0; i<size; i++)
  tabC[i] = tabA[i] = tabC[tabA[i]] + 1;
  for (i = 1; i < z+1; i++)
  tabC[i] = tabC[i] + tabC[i-1];
  for (i = size-1; i> -1; i--)
  {
    tabB[tabC[tabA[i]]] = tabA[i];
    tabC[tabA[i]] = tabC[tabA[i]] - 1;
    }


int* read(char *filename, int &size)     //funkcja odczytywania danych z pliku,gdzie argumentem jest
                                         //nazwa pliku oraz rozmiar,ktory "wychodzi" w trakcie wykonywania tej funkcji
{
   FILE *file;    //deklaracja pliku
   int k, *tab;

   size=0;
   file=fopen(filename,"r");      //  otworzenie pliku
   if(file==NULL)                 //sprawdzanie czy plik zostal otwarty prawidlowo
      return NULL;

   while(fscanf(file,"%d",&k)!=EOF)
      size++;

   tab=new int[size];              //tablica dynamiczna
   rewind(file);

   size=0;
   while(fscanf(file,"%d",&k)!=EOF)&n bsp;     //odczyt danych z pliQ
      tab[size++]=k;

   fclose(file);
   return tab;
}

void write(char *filename, int *tab, int size)
{
   FILE *file;

   file=fopen(filename,"w");        //otworzenie pliku
   if(file==NULL)
      return;

   for(int i=0;i<size;i++)
      fprintf(file,"%d\n",tab[i]);         //zapis danych do pliku

   fclose(file);
}


//wykonywanie programu
int main()
{
   int *tab;
   int size;

   tab=read("wejscie.dat",size);
   if(tab==NULL)
   {
      printf("nie można otworzyć pliku wejsciowego\n");
      return 1;
   }

   if(size<1)
   {
      printf("w pliku wejsciowym nie ma danych\n");
      return 2;
   }

   qsort(tab,0,size-1);

   write("wynik.dat",tab,size);

   return 0;
}




z gory dziekuje za odp!
pozdrawiam!!!

Gi
  
Re: sortowanie liniowe - znow problem :( (c++)
PostWysłano: Sobota, 15 Maj 2004, 14:37 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




hm troche przerobilam program , przeciez nie moze funkcja nic nie zwracac jak wpisywalam return..,no ale i tak nadal nie dziala;(

Kod:



#include <stdio.h>


void sort (int)
{
int z,i,size;
int tabA[size-1];
int tabB[size-1];
int tabC[z];
//szukanie najw. elem.
z=0;

for (i=0; i<size; i++)
  if (tabA[i]>z)
  z = tabA[i];

  //algorytm sort liniowego

  for (i=0; i < z+1; i++)
  tabC[i] = 0;
  for (i=0; i<size; i++)
  tabC[i] = tabA[i] = tabC[tabA[i]] + 1;
  for (i = 1; i < z+1; i++)
  tabC[i] = tabC[i] + tabC[i-1];
  for (i = size-1; i> -1; i--)
  {
    tabB[tabC[tabA[i]]] = tabA[i];
    tabC[tabA[i]] = tabC[tabA[i]] - 1;
    }





int* read(char *filename, int &size)     //funkcja odczytywania danych z pliku,gdzie argumentem jest
                                         //nazwa pliku oraz rozmiar,ktory "wychodzi" w trakcie wykonywania tej funkcji
{
   FILE *file;    //deklaracja pliku
   int k, *tabA;

   size=0;
   file=fopen(filename,"r");      //  otworzenie pliku
   if(file==NULL)                 //sprawdzanie czy plik zostal otwarty prawidlowo
      return NULL;

   while(fscanf(file,"%d",&k)!=EOF)
      size++;

   tabA=new int[size];              //tablica dynamiczna
   rewind(file);

   size=0;
   while(fscanf(file,"%d",&k)!=EOF)&n bsp;     //odczyt danych z pliQ
      tabA[size++]=k;

   fclose(file);
   return tabA;
}

void write(char *filename, int *tab, int size)
{
   FILE *file;

   file=fopen(filename,"w");        //otworzenie pliku
   if(file==NULL)
      return;

   for(int i=0;i<size;i++)
      fprintf(file,"%d\n",tabB[i]);         //zapis danych do pliku

   fclose(file);
}


//wykonywanie programu
int main()
{
   int *tabA, int *tabB;
   int size;

   tabA=read("wejscie.dat",size);
   if(tabA==NULL)
   {
      printf("nie można otworzyć pliku wejsciowego\n");
      return 1;
   }

   if(size<1)
   {
      printf("w pliku wejsciowym nie ma danych\n");
      return 2;
   }

   qsort(tabB,0,size-1);      // tab b czy A??

   write("wynik.dat",tabB,size);

   return 0;
}



hm..
  
Re: <studentka> sortowanie liniowe - znow problem :( (
PostWysłano: Sobota, 15 Maj 2004, 14:50 Odpowiedz bez cytowania Odpowiedz z cytatem
Tirinti
Pro uczestnik
<tt>Pro uczestnik</tt>
 
Użytkownik #28
Posty: 1295


[ Osobista Galeria ]




Szczerze mówiąc pierwsze słyszę o sortowaniu liniowym.
Znalazłem cośtakiego.
http://www.google.pl/search?q=cache:W1VbBL0MZ_IJ:www.polsl.gliwice.pl/ ~saveman/_eng/algos/03-02-10_linear.htm+%22sortowanie+liniowe%22&h l=pl

Jeśli to o to chodzi to tam jest odpowiedź.
Kod:

template <class T>
void LinearSort(T *tab,int n)
{
   int i;
   T t;
   for(i=0; i<n; i++)
   {
      while(tab[i]!=i)
      {
         t = tab[i];
         tab[i] = tab[tab[i]];
         tab[tab[i]] = t;
      }
   }
}


W przypadku liczb całkowitych to będzie
Kod:

void LinearSort(int *tab, int n)
{
   int i,t;
   for(i=0; i<n; i++)
   {
      while(tab[i]!=i)
      {
         t = tab[i];
         tab[i] = tab[t];
         tab[t] = t;
      }
   }
}


Ale w przypadku kiedy sortuje się same liczby rzeczywiste a nie jakieś struktury po kluczu, będącym liczbą rzeczywistą, to wystarczy
Kod:

void LinearSort(int *tab, int n)
{
   for(int i=0; i<n; i++)
      tab[i]=i;
}



Oczywiście miałem na myśli liczby całkowite a nie rzeczywiste :)[[/b]
  
Re: <studentka> sortowanie liniowe - znow problem :( (
PostWysłano: Sobota, 15 Maj 2004, 14:55 Odpowiedz bez cytowania Odpowiedz z cytatem
Tirinti
Pro uczestnik
<tt>Pro uczestnik</tt>
 
Użytkownik #28
Posty: 1295


[ Osobista Galeria ]




Z pewnościąbrakuje } a i trochę wcięć by się przydało. :)
A jeszcze lepiej jakiś link do opisu tego algorytmu, bo chyba chodzi o cośinnego niż znalazłem.
  
Re: sortowanie liniowe - znow problem :( (c++)
PostWysłano: Sobota, 15 Maj 2004, 16:06 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




link juz podaje:

http://150.254.21.130/infos/pp2inf/Sortowanie_w_czasie_liniowym.pdf

hm tylko koles zle podal ,bo jeszcze przy tablicach tzreba odjac 1..

teraz zaczelam robic to troche inaczej..


Kod:

#include <stdio.h>
#include <fstream.h>
#include <iostream.h>

int* laduj(int &ile,int* tabA);
void zapisz(int ile, int* tabB);

int main(void)
{
int ile,k,i;
   int tabA[ile-1];
  int tabB[ile-1];
  int *tabA = laduj(ile,tabA);

   //szukanie najw. elem.
k=0;

for (i=0; i<ile; i++)
  if (tabA[i]>k)
  k = tabA[i];

  //tablica pomocnicza

  int tabC[k];

  //algorytm sort liniowego

  for (i=0; i < k+1; i++)
  tabC[i] = 0;
  for (i=0; i<ile; i++)
  tabC[i] = tabA[i] = tabC[tabA[i]] + 1;
  for (i = 1; i < k+1; i++)
  tabC[i] = tabC[i] + tabC[i-1];
  for (i = ile-1; i> -1; i--)
  {
    tabB[tabC[tabA[i]]] = tabA[i];
    tabC[tabA[i]] = tabC[tabA[i]] - 1;
    }

    int* wczytaj(int &ile,int* tabA)
{
ifstream plik;
plik.open("dane.txt",ios::in);

plik >> ile;

tabA  = new int[ile];

for (int i=0;i<ile;i++)
{
plik >> tabA[i];
}

plik.close();
return tabA;

}

void zapisz(int ile, int* tabB)
{
ofstream plik;
plik.open("dane.txt",ios::out);

plik << ile << endl;   //ile w pliku jest wpisow

for (int i=0; i<ile; i++)
{
plik << tabB[i] << endl;
}

plik.close();
}



teraz to juz kombinuje :)

pozdrawiam!
  
Re: sortowanie liniowe - znow problem :( (c++)
PostWysłano: Sobota, 15 Maj 2004, 16:12 Odpowiedz bez cytowania Odpowiedz z cytatem
Tassadar
Kapitan Heh
 
Użytkownik #3
Posty: 246


[ Osobista Galeria ]




mowa o counting sort - sortowanie przez zliczanie - warunek jest taki ze wiemy z jakiego przedzialu sa liczby.
Kod:
//parametry to wskaznik do tablicy, liczba elementow, roznica miedzy elementem max i min
void CountingSort(int *A,int n,int k){
  int i,m,R[n],C[k];
  for(i=0,m=A[0];i<n;i++)
    if(A[i]<m)
      m=A[i];
  for(i=0;i<k;i++)
    C[i]=0;
  for(i=1;i<n;i++)
    C[A[i]-m]++;
  for(i=1;i<k;i++)
    C[i]+=C[i-1];
  for(i=n-1;i>=0;i--){
    R[C[A[i]-m]]=A[i];
    C[A[i]-m]--;
  }
 
  for(i=0;i<n;i++)
    A[i]=R[i];
  /********
  mozna ostatatia petle zastapic przez:
  return R;
  i odpowiednio zmienic wywolanie
  ********/
}


Tam gdzie mowisz, studentko, zwracac powinno byc raczej otrzymywac (parametry). Latwiej mi dac gotowy kod niz analizowac twoj.. ci chyba tez.
Zwracam uwage, ze w wywolaniu podajesz dlugosc tablicy, a nie, tak jak w quicksort, index ostatniego.
  
Re: sortowanie liniowe - znow problem :( (c++)
PostWysłano: Sobota, 15 Maj 2004, 16:24 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




dzieki hm ja to mam problemy z tym zapisem o odczytywaniem zpliku chyba;/

sam algorytm mi chodzi , tak napisalam

Kod:

#include <stdio.h>

main()
{
int z,i,size;
int tabA[size-1];
int tabB[size-1];
int tabC[z];
//szukanie najw. elem.
z=0;

for (i=0; i<size; i++)
  if (tabA[i]>z)
  z = tabA[i];

  //algorytm sort liniowego

  for (i=0; i < z+1; i++)
  tabC[i] = 0;
  for (i=0; i<size; i++)
  tabC[i] = tabA[i] = tabC[tabA[i]] + 1;
  for (i = 1; i < z+1; i++)
  tabC[i] = tabC[i] + tabC[i-1];
  for (i = size-1; i> -1; i--)
  {
    tabB[tabC[tabA[i]]] = tabA[i];
    tabC[tabA[i]] = tabC[tabA[i]] - 1;

   }
   }

  
Re: <studentka> sortowanie liniowe - znow problem :( (
PostWysłano: Sobota, 15 Maj 2004, 17:04 Odpowiedz bez cytowania Odpowiedz z cytatem
Tirinti
Pro uczestnik
<tt>Pro uczestnik</tt>
 
Użytkownik #28
Posty: 1295


[ Osobista Galeria ]




Ni emam tu kompilatora więc nie mogłem sprawdzić poprawności ale powinno być OK;
Kod:

int* sort(int *tabA, int n)
{
  int k(tab[0]),m(tab[0]),i;

  for(i=1; i<n; i++)
  {
    if(tabA[i]>k)
      k=tabA[i];
    if(tabA[i]<m)
      m=tabA[i];
  }

  k-=m;
  for(i=0;i<n;i++)
    tabA[i]-=m;

  int *tabB, *tabC;
  tabB=new int[n];
  tabC=new int[k+1];

  for(i=0;i<=k;i++)
    tabC[i]=0;

  for(i=0;i<n;i++)
    tabC[tabA[i]]++;

  for(i=0;i<k;i++)
    tabC[i+1]+=tabC[i];

  for(i=n-1;i>=0;i--)
  {
    tabB[tabC[tabA[i]]-1]=tabA[i];
    tabC[tabA[i]]--;
  }

  for(i=0;i<n;i++)
  {
    tabA[i]+=m;
    tabB[i]+=m;
  }

  delete tabC;
  return tabB;
}


A tu wersja trochę szybsza, ale nie jestem pewien czy pójdzie na ujemnych indeksach.
Kod:

int* sort(int *tabA, int n)
{
  int k(tab[0]),m(tab[0]),i,l;

  for(i=1; i<n; i++)
  {
    if(tabA[i]>k)
      k=tabA[i];
    if(tabA[i]<m)
      m=tabA[i];
  }

  l=k-m+1;

  int *tabB, *tabC;
  tabB=new int[n];
  tabC=new int[l];
  tabC-=m;

  for(i=0;i<=k;i++)
    tabC[i]=0;

  for(i=0;i<n;i++)
    tabC[tabA[i]]++;

  for(i=m;i<k;i++)
    tabC[i+1]+=tabC[i];

  for(i=n-1;i>=0;i--)
  {
    tabB[tabC[tabA[i]]-1]=tabA[i];
    tabC[tabA[i]]--;
  }

  tabC+=m;
  delete tabC;
  return tabB;
}
  
Re: sortowanie liniowe - znow problem :( (c++)
PostWysłano: Sobota, 15 Maj 2004, 17:27 Odpowiedz bez cytowania Odpowiedz z cytatem
studentka
Bywalec
<tt>Bywalec</tt>
 
Użytkownik #932
Posty: 25


[ Osobista Galeria ]




dzieki :)
  
sortowanie liniowe - znow problem :( (c++)
Forum dyskusyjne -> Software -> Programowanie :: WWW

Strona 1 z 1  
  
  
 Napisz nowy temat  Odpowiedz do tematu  
przeprowadzki warszawa
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