Sortowanie - podstawa zarządzania baz danych

[admin]

Sortowanie ma za zadanie uporządkowanie zbioru danych według zadanego kryterium. Zadane kryterium sortowania może być wartość liczby, pierwsza litera umieszczonego słowa, długość słowa.
Uwaga nieuporządkowana tablica nie pozwoli lub znacznie wydłuży wykonanie funkcji wyboru. Czyli np. na zrealizowanie polecenia wybrania z grupy osób o imieniu "Łukasz".

[admin]

Zadanie 1. Proszę utworzyć dwie tablice o dwuelementowe o nazwach A i B. Do pierwszej proszę wpisać z klawiatury dwie dowolne liczby. Do drugiej tablicy liczby powinny być automatycznie przepisane z tablicy A w porządku rosnącym. Wyświetlić zawartość obu tablic na ekranie.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{ int A[2],B[2];
int a,b,c;
for(a=0;a<=1;a++){
cout<<"Podaj "<<a+1<<" element tablcy A: "; cin>>A[a];}
if (A[1]<A[0]){B[0]=A[1];B[1]=A[0];} else {B[0]=A[0];B[1]=A[1];}
for(a=0;a<=1;a++){cout.width(3); cout<<A[a];}
cout<<endl;
for(a=0;a<=1;a++){cout.width(3); cout<<B[a];}   
cout<<endl;   
   
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Zadanie 2. Proszę utworzyć dwie tablice pozwalające na wprowadzenie trzech zmiennych o nazwach A i B. Do pierwszej proszę wpisać z klawiatury trzy dowolne liczby. Do drugiej tablicy liczby powinny być automatycznie przepisane z tablicy A w porządku rosnącym. Wyświetlić zawartość obu tablic na ekranie.


#include <cstdlib>
#include <iostream>

using namespace std;
int main(int argc, char *argv[])
{int z[3],b[3];
for (int c=0;c<3;c++){
    cout<<"Podaj "<<c+1<<" wartośc : ";cin>>z[c];}

if ((z[2]<=z[1]) &&(z[2]<=z[0])) {b[0]=z[2];
if (z[1]<=z[0]){b[1]=z[1];b[2]=z[0];}
else{b[1]=z[0]; b[2]=z[1];}}
else
if ((z[0]<=z[1]) &&(z[0]<=z[2])) {b[0]=z[0];
if (z[1]<=z[2]){b[1]=z[1];b[2]=z[2];} else{b[1]=z[2];b[2]=z[1];}}
else
if ((z[1]<=z[0]) &&(z[1]<=z[2])) {b[0]=z[1];
if (z[2]<=z[0]){b[1]=z[2];b[2]=z[0];} else{b[1]=z[0];b[2]=z[2];}};
 for(int c=0;c<=2;c++)
 {cout.width(4);cout<<z[c];}
 cout<<endl;
for(int d=0; d<=2;d++){cout.width(4);cout<<b[d];}   
    cout<<endl;
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Przedstawione powyżej algorytmy sortowania są skuteczne tylko dla niewielkiej liczby danych w tablicy. Powyżej trzech elementów tworzenie "drabinki if...if...if " wprowadza poważny chaos. Dlatego opracowano pewne techniki pozwalające na uporządkowanie zmiennych bez absorbowania zbyt dużej liczby zmiennych.
Pierwszym omawianym algorytmem sortowania jest algorytm sortowania bąbelkowego.
Algorytm sortowania bąbelkowego polega na porównywaniu par elementów leżących obok siebie i, jeśli jest to potrzebne, zmienianiu ich kolejności.
Czyli w pierwszym przebiegu porównujemy (i ewentualnie zamieniamy):

    1 - Element pierwszy i drugi
    2 Element drugi i trzeci
     ...
    n-ty  Element (n-1)-wszy i n-ty

Każdy element jest tak długo przesuwany w ciągu, aż napotkany zostanie element mniejszy od niego, wtedy w następnych krokach przesuwany jest ten mniejszy element.

[admin]

Zadanie 3. Proszę wprowadzić do tablicy trzy liczby i następnie posortować je w porządku rosnącym.Wykorzystać algorytm sortowania bąbelkowego

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{int a[3],b[3];
int r,y,z;
for(r=0;r<3;r++)
{cout<<"Podaj liczbę :";cin>>a[r];b[r]=a[r];  }

for(r=0;r<2;r++){
for(y=2;y>r;y--){
if(a[y]<a[y-1]){z=a[y];a[y]=a[y-1];a[y-1]=z;}                 
}}

for(r=0;r<3;r++)
{cout.width(4);cout<<a[r];}   
     
   cout<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Zadanie 4. Proszę wprowadzić do tablicy pięć liczb i następnie posortować je w porządku rosnącym.Wykorzystać algorytm sortowania bąbelkowego

[admin]

Zadanie 5. Napisać program wprowadzający do tablicy dane i sortujący tablicę o dowolnym wymiarze. Wykorzystać algorytm sortowania bąbelkowego

[admin]

Sortowanie korzystające z algorytmu : dziel i zwyciężaj.  Uwaga Opisywana jest metoda która w końcowej fazie wprowadza scalanie.

Ten sposób sortowania polega na dzieleniu zbiór danych na coraz mniejsze części i rozwiązywaniu problemów lokalnych. Jest to trochę niefortunne tłumaczenie algorytmu, bo moim zdaniem algorytm powinien nazywać się: dziel-rozwiąż-połącz.
Przedstawiany algorytm dziel i zwyciężaj wygląda następująco:
- Dziel- dzielimy ciąg na dwa i te dwie części jeszcze na dwie itd, do chwili uzyskania możliwości prostego sortowania
- Zwycieżaj - porządkuje utworzone przez dzielenie krótkie zbiory danych
- Połącz- łączy uporządkowane ciągi w jedną całość. 

[admin]

Inną metodą sortowania jest metoda sortowania nazywana szybką. Polega one na wybraniu liczby (tzw. elementu osiowego) ze zbioru  i przerzuceniu liczb mniejszych od wartości elementu osiowego na jego lewą stronę,  a większych elementów na prawą.

[admin]

Wywołanie funkcji pseudo losowej wersja1 .

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{int a[5]; int z;
srand(time(NULL));
for(int z=0;z<5;z++){
a[z]=1+rand()%100;};

for(int c=0;c<10,c++;){cout<<a[c]<<endl;};
    system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Zadanie. Program wpisujący do tablicy 5 liczb pseudolosowych. W tablicy liczby są sortowane rosnąco i wyświetlane na ekranie

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{int a[5]; int z1;
//losowanie
srand(time(NULL));
for(int z=0;z<5;z++){
a[z]=1+rand()%100;};
//wyświetlanie
for(z1=0;z1<5;z1++){cout<<a[z1]<<endl;};
cout<<endl;
//sortowanie
for(int s=0;s<5;s++){
for(int y=4;y>=s;y--)
{
if(a[y]<a[y-1]){z1=a[y];a[y]=a[y-1];a[y-1]=z1;}                 
}}

//wyświetlanie
for(z1=0;z1<5;z1++){cout<<a[z1]<<endl;};
    system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Zadanie Adam P _v1. Podobnie jak w poprzednim zadaniu lecz program wykorzystuje funkcje.

#include <cstdlib>
#include <iostream>

using namespace std;
int a[5]; int z1;

void los(int d[5])
{srand(time(NULL));
for(int z=0;z<5;z++){
a[z]=1+rand()%100;}};

void wysw(int d[5])
{for(z1=0;z1<5;z1++){cout<<a[z1]<<endl;}};
 
void sort(int d[5]){
for(int s=0;s<5;s++){
for(int y=4;y>=s;y--)
{
if(a[y]<a[y-1]){z1=a[y];a[y]=a[y-1];a[y-1]=z1;}                 
}};}

int main(int argc, char *argv[])
{
los(a);
wysw(a);
sort(a);
wysw(a);

  system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Zadanie Adam P _v2. Podobnie jak w poprzednim zadaniu lecz program wykorzystuje funkcje dodatkowo uporządkowano sprawę zmiennych.

#include <cstdlib>
#include <iostream>

using namespace std;


void los(int d[5])
{srand(time(NULL));
for(int z=0;z<5;z++){
d[z]=1+rand()%100;}};

void wysw(int d[5])
{for(int z1=0;z1<5;z1++){cout<<d[z1]<<endl;}};
 
void sort(int d[5]){
for(int s=0;s<5;s++){
for(int y=4;y>=s;y--)
{
if(d[y]<d[y-1]){int z1=d[y];d[y]=d[y-1];d[y-1]=z1;}                 
}};}

int main(int argc, char *argv[])
{int a[5];
los(a);
wysw(a);
sort(a);
wysw(a);

  system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Zadanie 1. Napisać program który do tablicy 10 elementowej wpisze 10 losowych liczb z zakresu od 6 do 18. Następnie posortuje je rosnąco.

include <cstdlib>
#include <iostream>

using namespace std;


void los(int d[5])
{srand(time(NULL));
for(int z=0;z<5;z++){
d[z]=6+rand()%12;}};

void wysw(int d[5])
{for(int z1=0;z1<5;z1++){cout<<d[z1]<<endl;}};
 
void sort(int d[5]){
for(int s=0;s<5;s++){
for(int y=4;y>=s;y--)
{
if(d[y]<d[y-1]){int z1=d[y];d[y]=d[y-1];d[y-1]=z1;}                 
}};}

int main(int argc, char *argv[])
{int a[5];
los(a);
wysw(a);
sort(a);
wysw(a);

  system("PAUSE");
    return EXIT_SUCCESS;
}
Zadanie 2. Podobnie jak poprzednie zadanie, ale wpisane do tablicy liczby nie mogą się powtarzać.
#include <cstdlib>
#include <iostream>

using namespace std;


void los(int d[10])
{srand(time(NULL)); int w[19]; for(int r=0;r<19;r++){w[r]=0;}
for(int z=0;z<10;){
int n=6+rand()%12;
if (w[n]==0){d[z]=n;z++;w[n]=1;}       
        }};

void wysw(int d[10])
{for(int z1=0;z1<10;z1++){cout<<d[z1]<<endl;}};
 
void sort(int d[10]){
for(int s=0;s<10;s++){
for(int y=9;y>=s;y--)
{
if(d[y]>d[y-1]){int z1=d[y];d[y]=d[y-1];d[y-1]=z1;}                 
}};}

int main(int argc, char *argv[])
{int a[10];
los(a);
wysw(a); cout<<endl<<endl;
sort(a);
wysw(a);

  system("PAUSE");
    return EXIT_SUCCESS;
}






Zadanie 3. Podobnie jak w zadaniu 2, tylko sortowanie od największej do najmniejszej.

Zadanie 4. Podobnie jak w zadaniu 3 , ale w funkcji głównej (main{}) wpisano tylko wywołanie funkcji zewnętrznych.

[admin]

Zadanie 7. Napisać program który losuje liczby od 0 do 50 i wyświetla je na ekranie. Jeżeli wylosowana zostanie liczba= 5 to losowanie zostaje zatrzymane. Stworzyć własną funkcję losowania.

#include <cstdlib>
#include <iostream>

using namespace std;
void los(void)
{srand(time(NULL));int n;int b;
for (b=1;
{n=rand()%51;
cout.width(4);cout<<n;
if (n==5){break;}
};cout<<endl;};
int main(int argc, char *argv[])
{los();
    system("PAUSE");
    return EXIT_SUCCESS;
}