|
| sortowanie liniowe - znow problem :( (c++) |
|
|
Wysłano: Sobota, 15 Maj 2004, 09:50 |
|
|
|
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++) |
|
|
Wysłano: Sobota, 15 Maj 2004, 14:37 |
|
|
|
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 :( ( |
|
|
Wysłano: Sobota, 15 Maj 2004, 14:50 |
|
|
|
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 :( ( |
|
|
Wysłano: Sobota, 15 Maj 2004, 14:55 |
|
|
|
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++) |
|
|
Wysłano: Sobota, 15 Maj 2004, 16:06 |
|
|
|
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++) |
|
|
Wysłano: Sobota, 15 Maj 2004, 16:12 |
|
|
|
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++) |
|
|
Wysłano: Sobota, 15 Maj 2004, 16:24 |
|
|
|
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 :( ( |
|
|
Wysłano: Sobota, 15 Maj 2004, 17:04 |
|
|
|
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++) |
|
|
Wysłano: Sobota, 15 Maj 2004, 17:27 |
|
|
|
|
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.
|