Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- HAKOWANIE
- #include <iostream>
- #include <time.h>
- using namespace std;
- const int n=20;
- int tab[n];
- void losuj(int tab[], int n)
- {
- srand(time(NULL));
- for(int i=0;i<n;i++)
- {
- tab[i]=rand()%100;
- }
- }
- void wypisz(int tab[], int n)
- {
- srand(time(NULL));
- for(int i=0;i<n;i++)
- {
- cout<<tab[i]<<" ";
- }
- cout<<endl;
- }
- void babelki(int t[], int n)
- {
- int Kres, i, k, tmp;
- Kres=n-1;
- do
- {
- i=0;
- k=-1;
- while(i<Kres)
- {
- if(t[i]>t[i+1])
- {
- tmp=t[i];
- t[i]=t[i+1];
- t[i+1]=tmp;
- k=i;
- }
- i++;
- }
- if(k>0)
- {
- Kres=k;
- }
- }
- while(k>0);
- }
- int poz_k(int t[], int n, int i)
- {
- int k=i;
- for(int j=i; j<n; j++)
- {
- if(t[k]>t[j])
- {
- k=j;
- }
- }
- return k;
- }
- void wybor(int t[], int n)
- {
- int k, tmp;
- for(int i=0; i<n-1; i++)
- {
- k=poz_k(t, n, i);
- tmp=t[i];
- t[i]=t[k];
- t[k]=tmp;
- }
- }
- int main()
- {
- cout<<"liczby losowane sa"<<endl;
- losuj(tab, n);
- wypisz(tab, n);
- cout<<"sortowanie babelkami"<<endl;
- babelki(tab, n);
- wypisz(tab, n);
- cout<<"sortowanie przez wybor"<<endl;
- wybor(tab, n);
- wypisz(tab, n);
- return 0;
- }
- NOTATKI
- Algorytm znajdowania minimum - min.
- \\Algorytm powinien posiadać specyfikacje czyli jakieś dane i wynik.
- Zbiór n liczb od a_1 do a_n.
- Wynik: min - najmniejszy element w zbiorze liczb.
- Krok1: za min przyjmij dowolny element ze zbioru.
- { zazwyczaj pierwszy
- Krok2: dla każdego innego elementu zbioru wykonuj:
- jeśli min>a_i to za min przyjmij a_i
- zaczynamy
- min=tab[0]
- for(int i=1 ;i<n ;i++)
- {
- if(min>tab[i])
- tab[i]=min
- }
- /////////////PRZERWA??????????????
- Dane: zbiór n liczb
- Wynik: min i max - odpowiednio najmniejszy i największy element ze zbioru n liczb
- Krok1: [podział zbioru na dwa podzbiory] połącz elementy zbioru w pary. Jeśli n jest liczbą nieparzystą to jeden element pozostaje wolny. Nazwijmy go z.
- Porównaj elementy w parach: Przypuścmy ze dla pary x i y, x > y, wówczas przenieś x do zbioru kandydatów na maximum. Oznaczmy go M, a y do zbioru kandydatów na minimum, oznaczmy go N.
- Krok2: Znajdź max w zbiorze M za pomocą algorytmu max. Znajdź min w zbiorze N za pomocą algorytmu min.
- Jeśli n jest nieparzyste, to jeśli z jest większe od max to za max przyjmij z. Jeśli z jest mniejsze od min to za min przyjmij z
- /////////////PRZERWA??????????????
- Dane: Zbiór liczb Z
- Wynik: min i max - odpowiednio największy i najmniejszy element w zbiorze Z
- Krok1: Jeśli zbiór Z składa się z jednego elementu to przyjmij jego wartość jednocześnie za min i max. Jeśli zbiór Z składa się z 2 elementów to wartości mniejszego z nich przypisz min,
- a większego przypisz max. W przeciwnym razie wykonuj:
- a) Podziel zbiór Z na dwa podzbiory Z1 i Z2 o tej samej lub niemal tej samej liczbie elementów
- b) Wykonaj ten sam algorytm dla (Z1, min1, max1)
- c) Wykonaj ten sam algorytm dla (Z2, min2, max2)
- d) Wartość mniejszej z liczb min1 i min2 przypisz min, a wartość większej z liczb max1 i max2 przypisz max
- /////////////PRZERWA??????????????
- Dane: Liczba naturalna n, Zbiór x_1, x_2, ... , x_n
- Wynik: Uporządkowanie od największej do najmniejszej
- Krok1: Kres:=n [Kres oznacza miejsce w ciągu oznaczającą granicę poszukiwania elementów do przestawienia]
- Krok2: Przyjmij i=1 oraz k=0
- Krok3: Dopóki i<Kres wykonuj: Jeśli x_i > x_i+1 to zamień te elementy miejscami i przyjmij k=i. Zwiększ i o 1 <== to po whilu
- Krok4: Jeśli k>1 przyjmij Kres=k i wróć do kroku drugiego. W przeciwnym razie zakończ algorytm
- /////////////PRZERWA??????????????
- Sortowanie przez wybór
- Dane: Liczba naturalna n, Zbiór x_1, x_2, ... , x_n
- Wynik: Uporządkowanie od największej do najmniejszej
- Krok1: Dla i=1, 2, ..., n-1 Wykonaj krok2 i krok3
- Krok2: Znajdź k takie że x_k jest najmniejszym elementem podciągu x_i do x_n
- Krok3: Zamień miejscami x_k z x_i
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement