 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
Do znających c/c++ - nie wiem co jest źle w programie :( , the_unicorn 22/10/03 21:12
Witajcie! Mam na jutro rano napisać program, który będzie sortował zawartość tablicy. Czyli użytkownik wprowadza np. 10 liczb a program za pomocą sortowania przez scalanie posortuje je i wyświetli w odpowiedniej kolejności. Udało mi się napisać to co poniżej, ale nie ukrywam, że w c dopiero zaczynam i być może błąd jest jakiś banalny. Z góry dziękuję za pomoc!
#include<stdio.h>
#include<stdlib.h>
int sortowanie(int tablica[], int lewy, int prawy);
int scalanie(int tablica[], int lewy, int srodek, int prawy);
int main()
{
int ilosc,i;
int tab_wpr[20];
int lewy,prawy;
printf("Program sosrtujacy.\n");
printf("Podaj ilosc liczb do posortowania.\n");
scanf("%d",&ilosc);
lewy=0;
prawy=ilosc;
printf("Podaj kolejno liczby.\n");
for(i=0; i<ilosc; i++)
scanf("%d",&tab_wpr[i]);
sortowanie(tab_wpr, lewy, prawy);
printf("%d",sortowanie);
return(0);
}
int sortowanie(int tablica[], int lewy, int prawy)
{
int w;
int srodek=(prawy+lewy)/2;
if (prawy-lewy>1)
{
sortowanie(tablica, lewy, srodek);
sortowanie(tablica, srodek+1, prawy);
w = scalanie(tablica, lewy, srodek, prawy);
}
return w;
}
int scalanie(int tablica[], int lewy, int srodek, int prawy)
{
int i=lewy,j=srodek,l=0;
int tab_temp[20];
while(i<=srodek && j<=prawy) {
if (tablica[i]<tablica[j])
tab_temp[l++]=tablica[i++];
else
tab_temp[l++]=tablica[j++];
}
while(i<=srodek)
tab_temp[l++]=tablica[i++];
for(i=0;i<j;i++)
tablica[i]=tab_temp[i];
return *tablica;
}"The wisest is he who knows he
does not know" - Poprawiłem część , maciusk 22/10/03 22:44
Poprawiłem część z wyświetlaniem wyników ale masz też błąd w funkcji sortującej, w którą nie chce mi się zagłębiać.MSI 683dx - ja dodam , atay 22/10/03 22:58
ze jestem w trakcie czytania Symfoni C++ i tam bardzo odradzał przypisania w postaci:
tab_temp[l++]=tablica[i++];
ponieważ jak to powiedział "różne kompilatory różnie to interpretują", dlatego najlepiej jest wrzucić tu tylko jedną inkrementację, drugą gdzie indziej. Funkcja przyznam skomplikowana, także nie widzę sensu zagłębiania się, chyba ze w jakims stopniu wyjasnisz jak ma dzialac :)_- Atay -_ - jeśli chodzi o funkcję scalającą to, , the_unicorn 22/10/03 23:21
ona ma dwie tablice - lewą i prawą, które są już posortowane przez funkcję sortującą. No i ona ma wybierać która liczba (tzn. z której talblicy) jest mniejsza i scalać ją w jedną tablicę tworząc w ten sposób jedną tablicę posortowaną. Jeśli skończy się któraś z połówek tablic (lewa lub prawa) to ma przepisać do nowej tablicy zawartość tej, która zawiera jeszcze liczby. A tak to jest wyjaśnione na jednej ze stron www:
merge-sort
Sortowanie przez scalanie opiera się na procedurze scalania dwóch ciągów rosnących. Najpierw wytłumaczę jak działa ta procedura scalania.
Mamy dwa ciągi rosnące:
1,2,3,3 oraz 2,7,7,11,14
"Zrobimy" z nich jeden ciąg rosnący. W tym celu porównujemy kolejne elementy obu ciągów wstawiając do tablicy (z ciągiem stanowiącym wynik tej operacji) tą z porównywanych liczb, która jest mniejsza. Potem przesuwamy "indeks porównywania" w tym ciągu, z którego pobraliśmy liczbę.
1,2,3,3 oraz 2,7,7,11,14
* *
Ponieważ 1<2, dopisujemy do trzeciego ciągu 1 i przesuwamy gwiazdkę w lewym ciągu o jedną pozycję.
1,2,3,3 oraz 2,7,7,11,14
* *
trzeci ciąg: 1
2=2, więc do trzeciego ciągu dopisujemy 2 i przesuwamy o pozycję gwiazdkę w lewym ciągu (np.).
1,2,3,3 oraz 2,7,7,11,14
* *
trzeci ciąg: 1,2
2<3, więc dopisujemy 2 i przesuwamy prawą gwiazdkę.
1,2,3,3 oraz 2,7,7,11,14
* *
trzeci ciąg: 1,2,2
3<7, więc dopisujemy 3 i przesuwamy lewą gwiazdkę.
1,2,3,3 oraz 2,7,7,11,14
* *
trzeci ciąg: 1,2,2,3
3<7, więc dopisujemy 3 i przesuwamy lewą gwiazdkę.
1,2,3,3 oraz 2,7,7,11,14
* *
trzeci ciąg: 1,2,2,3,3
Lewy ciąg się skończył, więc dopisujemy na koniec resztę prawego ciągu.
1,2,3,3 oraz 2,7,7,11,14
* *
trzeci ciąg: 1,2,2,3,3,7,7,11,14
No i mamy ciąg rosnący!
Żeby wykorzystać scalanie do sortowania, trzeba napisać rekurencyjną procedurę, której parametrem jest wycinek ciągu do posortowania. Jeśli fragment ciągu ma tylko jeden element, to nic nie robimy (w końcu to jest już posortowane!). Ten ciąg dzielimy na dwie równe (albo w przybliżeniu równe) części i sortujemy każdą z nich (rekurencja!). Po tej operacji mamy więc dwa ciągi rosnące. Scalamy je."The wisest is he who knows he
does not know"
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2026, TwojePC.PL |
 |
|
|
