 |
 | | problem z programem w cpp(qsort) :9 |
|
 |
 Wysłano: Poniedziałek, 10 Maj 2004, 10:08 |
  |
|
|
witam!!
mam do napisania program na lab.(na jutrzejsze popoludnie:() ewentualnie moge oddac za tydzien.,ale bedzie gorsza ocena..siedzialam caly weekend i nic mi nie wychodzi:(
tresc zadania brzmi:zaimplementuj alg w jezyku c/c++.. implementacja ma umozliwiac wczytywanie danych-l.typu calkowitego -z pliku oraz zapisywanie wynikow dzialania do pliku.Chodzi o alg.q sort.Moze ma ktos taki program.. albo moglby poprawic bl.w moim programie , bo ja juz nie mam sily:(.Bede bardzo wdzieczna!!
| Kod: |
#include <stdio.h>
void main()
{
FILE *we,*wy;
int ile=0,i,j,n,z;
char k;
int *tab;
z=0;
we=fopen("we","r");
do
{
fscanf(we,"%d",&k);
if (k!=32) ile++;
}
while (feof(we));
ile--;
tab = new int[ile];
rewind(we);
for (i=0; i < ile; i++)
{
fscanf(we,"%d",&tab[i]);
printf("%d",tab[i]);
}
void zamien(int u, int v)
{
int temp = tab[u];
tab[u] = tab[v];
int x,i,j;
x = tab[p]
tab[v] = temp;
}
int partition(int p, int r)
{]; //na przyklad; pierwszy element, jesli jest to element "skrajny", to podzielimy b. nierowno
//jesli zawsze bedzie to skrajny, to zlozonosc calego qsorta bedzie O(n^2)
i = p-1;
j = r+1;
while (1)
{
do j--; while (tab[j] > x); //wyszukaj element <= x
do i++; while (tab[i] < x); //wyszukaj element >= x
if (i<j) //kiedy jest sens
zamien(i,j);
else
return j; //koniec "lewej czesci"
}
}
void quicksort(int p, int r) // "dziel i zwyciezaj" - dzielimy przedzial (p,r) na 2 czesci i sortujemy je osobno
{
if (p<r)
//podziel (p,r) na 2 czesci, lewa "mniejsza" od prawej
{
int q = partition(p,r); //q - ostatni element lewej czesci
quicksort(p,q);
quicksort(q+1,r);
}
}
void sortuj()
{
quicksort(0,ile-1);
cout << "Posortowane." << endl;
}
wy=fopen("wynik","w");
void main()
{
for (i=0;i<ile;i++)
printf("%d", tab[i]);
printf("\n%d",z);
qsort(tab,0,n-1);
for (i=0;i<ile;i++)
printf("%d", tab[i]);
printf( "\n%d",z);
delete tab;
fclose(we);
fclose(wy);
getchar();
return 0;
}
|
pozdrawiam!!! |
|
|
|
|
 |
|
 |
|
| | Re: <studentka> problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 13:22 |
|
|
|
To co ty tam robisz to jest raczej merge-sort a nie quick-sort.
Zakłądam, że operacje na plikach masz prawidłowe. Sam od dawna w ANSI nie programowałem i niezbyt to pamiętam. Tak więc zamieszczam tylko prawidłową funkcję qsort i main pozwalającą na jej przetestowanie.
| Kod: |
int main(
{
int *tab;
int size;
tab=new int[10];
size=10;
tab[0]=71;
tab[1]=45;
tab[2]=93;
tab[3]=67;
tab[4]=34;
tab[5]=79;
tab[6]=36;
tab[7]=13;
tab[8]=68;
tab[9]=49;
qsort(tab,0,size-1);
for(int i=0; i<size; i++)
printf("%i \n",tab[i]);
return 0;
}
void qsort(int *tab, int l, int r)
{
int i,j,x,t;
i=l;
j=r;
x=tab[(i+j)/2];
while(i<j)
{
while(tab[i]<x)
i++;
while(tab[j]>x)
j--;
if(i<=j)
{
t=tab[i];
tab[i]=tab[j];
tab[j]=t;
i++;
j--;
}
}
if(l<j)
qsort(tab,l,j);
if(r>i)
qsort(tab,i,r);
}
|
|
|
|
|
|
|
|
|
|
| | Re: problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 14:18 |
|
|
|
zrobilam teraz inaczej..skompilowal sie,aale sie wiesza;/
| Kod: |
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void quicksort(int tablica[], int x, int y)
{
FILE *we, *wy;
int i,j,n,v,temp;
char k;
i=x;
j=y;
v=tablica[div(x+y,2).quot];
do
{
{
fscanf(we,"%d",&k);
if(k!=32) n++;
}
while(!feof(we));
n--;
printf("%d\n",n);
int *tablica = new int[n]; //tablica dynamiczna
rewind(we);
for(i=0;i<n;i++) fscanf(we,"%d",&tablica[i]); //petla pobierajaca elementy z pliku
for(i=0;i<n;i++) printf("%d ",tablica[i]);
printf("\n");
//algorytm sortowania
while (tablica[i]<v) i++;
while (v<tablica[j]) j--;
if (i<=j)
{
temp=tablica[i];
tablica[i]=tablica[j];
tablica[j]=temp;
i++;
j--;
}
}
while (i<=j);
if (x<j) quicksort(tablica,x,j);
if (i<y) quicksort(tablica,i,y);
}
void main(void)
{
FILE *we,*wy;
int ile_liczb,i,liczba;
int tablica[i];
clrscr;
printf("Ile liczb chesz posortowac ? ");
scanf("%i",&ile_liczb);
for(i=0; i<ile_liczb; i++)
{
printf("Wprowadz liczbe #%i: ",i+1);
scanf("%i",&liczba);
tablica[i]=liczba;
}
clrscr;
printf("Tablica przed posortowaniem:");
for(i=0; i<ile_liczb; i++)
{
printf("\n%i",tablica[i]);
}
we=fopen("wynik", "w");
quicksort(tablica,0, ile_liczb-1);
printf("\nTablica po posortowaniu:");
for(i=0; i<ile_liczb; i++)
{
printf("\n%i",tablica[i]);
}
delete tablica;
fclose(we);
fclose(wy);
getch();
}
|
a triniti dzieki:) pokombinuje jeszcze pozniej;)
pozdrawiam! |
|
|
|
|
|
|
|
|
| | Re: <studentka> problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 16:09 |
|
|
|
Wiesza się prawdopodobnie przez
while (i<=j);
jeśli warunek jest prawdziwy to to jest nieskończona pętla. |
|
|
|
|
|
|
|
|
| | Re: <Tirinti> problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 16:24 |
|
|
|
Przerobiłem wczięcia w twoim kodzie, żeby był bardziej czytelny.
To while jest od do, więc jest OK, ale chy ba brakuje innego do. Co by nie było jest to jakoś dziwnie zrobione.
| Kod: |
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void quicksort(int tablica[], int x, int y)
{
FILE *we, *wy;
int i,j,n,v,temp;
char k;
i=x;
j=y;
v=tablica[div(x+y,2).quot];
do
{
{
fscanf(we,"%d",&k);
if(k!=32) n++;
}
while(!feof(we));
n--;
printf("%d\n",n);
int *tablica = new int[n]; //tablica dynamiczna
rewind(we);
for(i=0;i<n;i++)
fscanf(we,"%d",&tablica[i]); //petla pobierajaca elementy z pliku
for(i=0;i<n;i++) printf("%d ",tablica[i]);
printf("\n");
//algorytm sortowania
while (tablica[i]<v)
i++;
while (v<tablica[j])
j--;
if (i<=j)
{
temp=tablica[i];
tablica[i]=tablica[j];
tablica[j]=temp;
i++;
j--;
}
}
while (i<=j);
if (x<j)
quicksort(tablica,x,j);
if (i<y)
quicksort(tablica,i,y);
}
void main(void)
{
FILE *we,*wy;
int ile_liczb,i,liczba;
int tablica[i];
clrscr;
printf("Ile liczb chesz posortowac ? ");
scanf("%i",&ile_liczb);
for(i=0; i<ile_liczb; i++)
{
printf("Wprowadz liczbe #%i: ",i+1);
scanf("%i",&liczba);
tablica[i]=liczba;
}
clrscr;
printf("Tablica przed posortowaniem:");
for(i=0; i<ile_liczb; i++)
{
printf("\n%i",tablica[i]);
}
we=fopen("wynik", "w");
quicksort(tablica,0, ile_liczb-1);
printf("\nTablica po posortowaniu:");
for(i=0; i<ile_liczb; i++)
{
printf("\n%i",tablica[i]);
}
delete tablica;
fclose(we);
fclose(wy);
getch();
}
|
|
|
|
|
|
|
|
|
|
| | Re: <Tirinti> problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 17:12 |
|
|
|
Proponuję coś takiego.
| Kod: |
#include "stdafx.h"
void qsort(int *tab, int l, int r)
{
int i,j,x,t;
i=l;
j=r;
x=tab[(i+j)/2];
while(i<j)
{
while(tab[i]<x)
i++;
while(tab[j]>x)
j--;
if(i<=j)
{
t=tab[i];
tab[i]=tab[j];
tab[j]=t;
i++;
j--;
}
}
if(l<j)
qsort(tab,l,j);
if(r>i)
qsort(tab,i,r);
}
int* read(char *filename, int &size)
{
FILE *file;
int k, *tab;
size=0;
file=fopen(filename,"r");
if(file==NULL)
return NULL;
while(fscanf(file,"%d",&k)!=EOF)
size++;
tab=new int[size];
rewind(file);
size=0;
while(fscanf(file,"%d",&k)!=EOF)
tab[size++]=k;
fclose(file);
return tab;
}
void write(char *filename, int *tab, int size)
{
FILE *file;
file=fopen(filename,"w");
if(file==NULL)
return;
for(int i=0;i<size;i++)
fprintf(file,"%d\n",tab[i]);
fclose(file);
}
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;
}
|
Wczytuje, sortuje i zapisuje. |
|
|
|
|
|
|
|
|
| | Re: problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 23:34 |
|
|
|
wielkie dzieki..;****
a co to za biblioteka?? pierwszyraz ja widze;)
pozdrawiam goraco!! |
|
|
|
|
|
|
|
|
| | Re: problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Poniedziałek, 10 Maj 2004, 23:56 |
|
|
|
| studentka @ Poniedziałek, 10 Maj 2004 23:34 @ : |
a co to za biblioteka?? pierwszyraz ja widze;)
|
A google wylaczyli  Czyta i sie uczy |
|
|
|
|
|
|
|
|
| | Re: <studentka> problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Wtorek, 11 Maj 2004, 11:22 |
|
|
|
| Zrobiłem copy-paste z Visuala. W ANSI powinno być stdio.h i null małymi literami. |
|
|
|
|
|
|
|
|
| | Re: problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Wtorek, 11 Maj 2004, 15:40 |
|
|
|
heh dzieki juz sie domyslilam,teraz wlasnie mam lab.i nastepny algorytm..przez zliczanie;/ a potem kubelki;/
pozdro! |
|
|
|
|
|
|
|
|
| | Re: problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Środa, 12 Maj 2004, 00:07 |
|
|
|
kod studentki to tez proba quick sorta - w merge tablice sa scalane.
Oba wg mnie niewydajne. Quicksort powinien miec srednia zlozonosc n*lgn, a te maja najmniej n^2 (nie ma potrzeby zagniezdzac petli).
Moja wersja:
| Kod: |
void zamien(int *a, int *b){
int temp=*a;
*a=*b;
*b=temp;
}
/* dzieli tablice zgodnie z quicksortem (mniejsze na lewo, wieksze na prawo)
parametry: wskaznik na tablice, lewy index podtablicy, prawy index podtablicy */
int part(int *T, int l, int p){
int x=T[p];
int j,i=l;
while(T[i]<=x && i<=p)
i++;
for(j=i+1;j<=p;j++)
if(T[j]<=x)
zamien(&T[j],&T[i++]);
return i-1;
}
/* sortuje tablice
parametry: wskaznik na tablice, lewy index podtablicy, prawy index podtablicy */
void quick(int *T, int l, int p){
int srodek;
if(l<p){
srodek=part(T,l,p); /*dzielimy...*/
quick(T,l,srodek-1);
quick(T,srodek+1,p);
}
} |
wywolujemy quick(T,0,max-1); |
|
|
|
|
|
|
|
|
| | Re: <Tassadar> problem z programem w cpp(qsort) :9 |
|
|
| Wysłano: Środa, 12 Maj 2004, 10:22 |
|
|
|
Złożoność jest ta sama. Zauważ, że to nie jest zagnieżdżenie pętli n przebiegów w pętli n przebiegów. Zewnętrzna pętla tylko sprawdza, czy wewnętzna przeszła n elementów, jak tak to koniec, jak nie to wewnętżna kontynuuje.
Twoja wersja ma szansę działać sybciej, bo ma mniej instrukcji warunkowych. Ale to będzie tylko liniowy przyrost prędkości.
Natomiast nie widzę potrzeby dzielenia na 3 funkcje, skoro part i zamień są wywoływane tylko w jednym miejscu.
A wogóle to najlepiej zrezygnować z rekurencji, bo przy durzej ilości elementów przepełni się stos. |
|
|
|
|
|
