Ĺadny brzuch
KOD:
Void InsertSort (int*tab) { for (int i=1; i<n; i++) { int j=i; int temp=tab[j]; While ((j>0)&&(tab[j-1]>temp)) { tab[j] = tab[j-1]; j--; } tab[j]=temp; }}
Więc tak, jest to kod, który otrzymałem i ma być to procedura sortująca przez wstawianie.
Skoro dostałem taki kod mam na jego podstawie napisać program. Teoretycznie rozumiem ten kod,
umiem to przetłumaczyć, ale nie mogę się doszukać jak to może posortować liczby i co musi mi
użytkownik podać na wejściu. Poza tym, chociaż bardzo chcę, nikt mi nie chce wytłumaczyć wskaźników.
Więc proszę o pomoc w zrozumieniu tego kodu (we wtorek mam zajęcia z infy) oraz mam dwa pytania nie związane z kodem ale jak najbardziej z tematem:
1. Co to znaczy int*tab i jak to działa?
2. Co to znaczy, że sortowanie przez wstawianie jest algorytmem klasy O(N2)?
Pozdrawiam wszystkich forumowiczów, a szczególnie tych którzy mi pomogą.
ad1. jest to wskaznik do tablicy "intow" czyli liczb calkowitych
ad2. ten symbol oznacza zlozonosc... wzor na nia, dokladniej... tak wiec w tym przypadku zlozonosc jest dwa razy wieksza niz ilosc symboli do posortowania
algorytm "przesuwa" element dopoki nie napotka "mniejszego z lewej" ;) wyprobuj to na kartce - dziala, zapewniam!
2. Co to znaczy, że sortowanie przez wstawianie jest algorytmem klasy O(N2)?
Chodziło Ci o O(n2) - czyli złożoność kwadratową - wytłumaczyłem tam: http://forum.ks-eksp...mp;#entry796502
ad2. ten symbol oznacza zlozonosc... wzor na nia, dokladniej... tak wiec w tym przypadku zlozonosc jest dwa razy wieksza niz ilosc symboli do posortowania
Zgiń przepadnij. :P
Nie możesz powiedzieć, że złożoność jest "dwa razy większa", bo złożoność może być logarytmicza, liniowa, liniowo-logarytmiczna, wielomianowa albo wykładnicza. Zapis z dużym "O" (a nie wzór) to tylko symboliczny, skrótowy zapis złożoności, odpowiednio: O(lg n), O(n), O(n lg n), O(nk) albo O(kn). Zapis O(2n), a tym bardziej O(n2), to już raczej "liczba operacji", a nie złożoność.
A co do działania algorytmu, to bierz kartkę, włącz w mózgu emulator x86 i rysuj.
Ja zadałem pytanie odnośnie tego też co muszę dostać na wejściu, ponieważ tego nie wiem (która zmienna jest za co) to ciężko mi rozpisać ten algorytm na kartce.
Napisaliście, że jest to wskaźnik, a ja pytałem jakie on zadanie spełnia. Swoją drogą teraz, zanim mi odpowiecie, to poprubuje jeszcze raz ale nie wiem. ;-)
Użytkownik matthev edytował ten post 04 listopad 2007, 12:00
wejsciem jest tablica intow "tab"
czyli użytkownik ma mi podać ile liczb ma posortować i potem kolejne elmenty tablicy, rozumiem że n
to ma być liczba elementów, a numerem elementu ma być j. I użytkownik ma mi przed rozpoczęciem procedury to wszystko podać tak?
I jak mam po procedurze wypisać posortowane liczby. Oczywiście znam i printf i cout ale chodzi o moment.
Najgorsze jest to że ja dostałem tylko fragment programu i nie wiem co zrobić przed i po procedurze.
Użytkownik matthev edytował ten post 04 listopad 2007, 15:05
posortowane dane wroca do tablicy "tab"... niepokojacy jest brak "jawnego" przekazania zmiennej "n"... powinna ona wystapic w naglowku, jako ilosc zmiennych do sortowania... albo wewnatrz procedury, pobierac dlugosc tablicy
w takim przypadku wyglada na to, ze jest ona zadeklarowana globalnie i moze (przy brzydkim stylu programowania) zawierac cokolwiek, bo moge tego "n" uzywać gdzie chce!
Czyli ma być tak? :
1. pyatm się użytkownika o ilość liczb do posortowania, zapisuję daną w zmiennej n
2. pytam się o kolejne elementy tablicy tak długo aż n będzie zerem
3. przepisuję procedurę
4. wypisuję wynik
ALE MAM PYTANIE, W KTÓRYM MIEJSCU I JAK PYTAĆ O WARTOŚĆ ELEMENTÓW TABLICY, I GDZIE I JAK WYŚWIETLIĆ WYNIK.
Czyli jaki powinien być szkielet takiego programiku. I jak ta procedura ma przekazać wynik swojej pracy?
Użytkownik matthev edytował ten post 05 listopad 2007, 19:52
ELEMENTÓ
o żesz :omg:
Czyli jaki powinien być szkielet takiego programiku.
1. Info dla kompilatora co ma dołączyc (#include...)
2. Deklaracja funkcji dodatkowych (u ciebie void InsertSort)
3. Deklaracja funkcji int main, zawierającej
- wczytanie n
- dopóki n!=0 wczytywanie liczby do kolejnego elementu tablicy
- wywołanie funkcji InsertSort, która w argumencie przyjmuje wskaźnik na tablicę
- wypisanie tablicy
I jak ta procedura ma przekazać wynik swojej pracy?Â
Nie procedura, tylko funkcja. Ona przyjmuje wskaźnik - czyli wskazujesz jej: "Te, funkcja! Patrz, tam leży tablica, weź mi ją posortuj!" - a ona potulnie lezie do tablicy, robi jej fiku-miku i zostawia ją posortowaną. Czyli ty musisz później tylko wypisać tą tablicę, bo ona już została posortowana.
Użytkownik bryn edytował ten post 04 listopad 2007, 20:23
Dzięki za pomoc, napiszę sobie cały program na podstawie twoich instrukcji i tu napiszę. A ty powiesz czy dobrze.
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Void InsertSort (int*tab) { for (int i=1; i<n; i++) { int j=i; int temp=tab[j]; While ((j>0)&&(tab[j-1]>temp)) { tab[j] = tab[j-1]; j--; } tab[j]=temp; }}
Więc tak, jest to kod, który otrzymałem i ma być to procedura sortująca przez wstawianie.
Skoro dostałem taki kod mam na jego podstawie napisać program. Teoretycznie rozumiem ten kod,
umiem to przetłumaczyć, ale nie mogę się doszukać jak to może posortować liczby i co musi mi
użytkownik podać na wejściu. Poza tym, chociaż bardzo chcę, nikt mi nie chce wytłumaczyć wskaźników.
Więc proszę o pomoc w zrozumieniu tego kodu (we wtorek mam zajęcia z infy) oraz mam dwa pytania nie związane z kodem ale jak najbardziej z tematem:
1. Co to znaczy int*tab i jak to działa?
2. Co to znaczy, że sortowanie przez wstawianie jest algorytmem klasy O(N2)?
Pozdrawiam wszystkich forumowiczów, a szczególnie tych którzy mi pomogą.
ad1. jest to wskaznik do tablicy "intow" czyli liczb calkowitych
ad2. ten symbol oznacza zlozonosc... wzor na nia, dokladniej... tak wiec w tym przypadku zlozonosc jest dwa razy wieksza niz ilosc symboli do posortowania
algorytm "przesuwa" element dopoki nie napotka "mniejszego z lewej" ;) wyprobuj to na kartce - dziala, zapewniam!
2. Co to znaczy, że sortowanie przez wstawianie jest algorytmem klasy O(N2)?
Chodziło Ci o O(n2) - czyli złożoność kwadratową - wytłumaczyłem tam: http://forum.ks-eksp...mp;#entry796502
ad2. ten symbol oznacza zlozonosc... wzor na nia, dokladniej... tak wiec w tym przypadku zlozonosc jest dwa razy wieksza niz ilosc symboli do posortowania
Zgiń przepadnij. :P
Nie możesz powiedzieć, że złożoność jest "dwa razy większa", bo złożoność może być logarytmicza, liniowa, liniowo-logarytmiczna, wielomianowa albo wykładnicza. Zapis z dużym "O" (a nie wzór) to tylko symboliczny, skrótowy zapis złożoności, odpowiednio: O(lg n), O(n), O(n lg n), O(nk) albo O(kn). Zapis O(2n), a tym bardziej O(n2), to już raczej "liczba operacji", a nie złożoność.
A co do działania algorytmu, to bierz kartkę, włącz w mózgu emulator x86 i rysuj.
Ja zadałem pytanie odnośnie tego też co muszę dostać na wejściu, ponieważ tego nie wiem (która zmienna jest za co) to ciężko mi rozpisać ten algorytm na kartce.
Napisaliście, że jest to wskaźnik, a ja pytałem jakie on zadanie spełnia. Swoją drogą teraz, zanim mi odpowiecie, to poprubuje jeszcze raz ale nie wiem. ;-)
Użytkownik matthev edytował ten post 04 listopad 2007, 12:00
wejsciem jest tablica intow "tab"
czyli użytkownik ma mi podać ile liczb ma posortować i potem kolejne elmenty tablicy, rozumiem że n
to ma być liczba elementów, a numerem elementu ma być j. I użytkownik ma mi przed rozpoczęciem procedury to wszystko podać tak?
I jak mam po procedurze wypisać posortowane liczby. Oczywiście znam i printf i cout ale chodzi o moment.
Najgorsze jest to że ja dostałem tylko fragment programu i nie wiem co zrobić przed i po procedurze.
Użytkownik matthev edytował ten post 04 listopad 2007, 15:05
posortowane dane wroca do tablicy "tab"... niepokojacy jest brak "jawnego" przekazania zmiennej "n"... powinna ona wystapic w naglowku, jako ilosc zmiennych do sortowania... albo wewnatrz procedury, pobierac dlugosc tablicy
w takim przypadku wyglada na to, ze jest ona zadeklarowana globalnie i moze (przy brzydkim stylu programowania) zawierac cokolwiek, bo moge tego "n" uzywać gdzie chce!
Czyli ma być tak? :
1. pyatm się użytkownika o ilość liczb do posortowania, zapisuję daną w zmiennej n
2. pytam się o kolejne elementy tablicy tak długo aż n będzie zerem
3. przepisuję procedurę
4. wypisuję wynik
ALE MAM PYTANIE, W KTÓRYM MIEJSCU I JAK PYTAĆ O WARTOŚĆ ELEMENTÓW TABLICY, I GDZIE I JAK WYŚWIETLIĆ WYNIK.
Czyli jaki powinien być szkielet takiego programiku. I jak ta procedura ma przekazać wynik swojej pracy?
Użytkownik matthev edytował ten post 05 listopad 2007, 19:52
ELEMENTÓ
o żesz :omg:
Czyli jaki powinien być szkielet takiego programiku.
1. Info dla kompilatora co ma dołączyc (#include...)
2. Deklaracja funkcji dodatkowych (u ciebie void InsertSort)
3. Deklaracja funkcji int main, zawierającej
- wczytanie n
- dopóki n!=0 wczytywanie liczby do kolejnego elementu tablicy
- wywołanie funkcji InsertSort, która w argumencie przyjmuje wskaźnik na tablicę
- wypisanie tablicy
I jak ta procedura ma przekazać wynik swojej pracy?Â
Nie procedura, tylko funkcja. Ona przyjmuje wskaźnik - czyli wskazujesz jej: "Te, funkcja! Patrz, tam leży tablica, weź mi ją posortuj!" - a ona potulnie lezie do tablicy, robi jej fiku-miku i zostawia ją posortowaną. Czyli ty musisz później tylko wypisać tą tablicę, bo ona już została posortowana.
Użytkownik bryn edytował ten post 04 listopad 2007, 20:23
Dzięki za pomoc, napiszę sobie cały program na podstawie twoich instrukcji i tu napiszę. A ty powiesz czy dobrze.