24.11.2.24011720. Napisati program koji će napuniti niz od “n“ elemenata slučajnim brojevima u rasponu od 1 do 1000 pri čemu se “n“ zadaje sa tastature (pri tome, “n“ neće biti veći od 100000) i ispisati elemente niza razdvojene jednim razmakom. Program zatim treba da sortira niz u opadajući poredak BubbleSort postupkom, i da ponovo ispiše elemente sortiranog niza. Također treba ispisati i vrijeme u sekundama potrebno za sortiranje (koristite funkciju “time“ iz biblioteke “ctime”). Program treba napisati modularno, uz pomoć 3 funkcije: “GenerirajNiz“ sa četiri parametra “p1”, “p2”, “a“ i “b“ koja treba da napuni cjelobrojni niz elemenata omeđen pokazivačima “p1” i “p2” (“p1” pokazuje na prvi element a “p2” na mjesto iza posljednjeg elementa) slučajnim brojevima u opsegu od “a“ do “b”, zatim “SortirajNiz“ sa dva parametra “p1” i “p2” koja treba da sortira niz omeđen pokazivačima “p1” i “p2” BubbleSort postupkom, i “IspisiNiz“ sa dva parametra “p1” i “p2” koja treba da ispiše elemente niza omeđene ovim pokazivačima.
Program prvo testirajte na malim vrijednostima “n“, da se uvjerite da funkcionira ispravno. Zatim testirajte vrijeme izvršavanja programa za 10000, 20000, 30000, 40000, 50000 i 60000 elemenata niza (pri tome, isključite poziv funkcije za ispis rezultata, da ne prikazujete gomilu brojeva na ekranu) i zabilježite rezultate u svesku. Uočite da je vrijeme izvršavanja približno proporcionalno kvadratu broja elemenata i odredite faktor proporcionalnosti (Napomena: rezultat će ovisiti od brzine računara na kojem vršite testiranje).
Ponovite sve što je traženo u zadatku 17.1, (vidi prethodni tekst) samo uz korištenje prvo InsertSort, a zatim i QuickSort postupka sa izborom slučajnog elementa kao pivota. Testiranje u oba slučaja izvršite za iste vrijednosti “n“ kao u zadatku 17.1 i zaključke upišite u svesku. U svesku ne treba prepisivati čitav program, već samo izmijenjene funkcije “SortirajNiz“ za oba slučaja.

Opis rješenja:

Listing programa:

#include <iostream>
#include <conio.h>
#include <cstdlib>
#include <ctime>
using namespace std;

void generirajniz(int *p1,int *p2,int a,int b){
while(p1<p2){
   *p1=a+rand()%(b-a+1);
    p1++;
    }
}

void sortniz(int *p,int *k){
for(int *i=p;i<<k-1;i++){
    int a=*(i+1);
    int *j;
    for(j=i+1;j>p&&*(j-1)<a;j--)
        *j=*(j-1);
    *j=a;
    }
    
}

void sortniz2(int *p,int *k){
if(p+1>=k)return;
int pivot=*(p+rand()%(k-p));
int *l=p,*d=k-1;
    while(l<=d){
        while(*l>pivot)l++;
        while(*d<pivot)d--;
        if(l<=d){
            int a=*l;
            *l=*d;
            *d=a;
            l++;
            d--;
        }
    }
sortniz2(p,d+1);
sortniz2(l,k);
}

void ispisiniz(int *p,int *k){
for(int *i=p;i<k;i++)
    cout<<*i<<"  ";
}

int main(){
srand(time(0));
int Niz[50],n,a,b;
cin>>n>>a>>b;
generirajniz(Niz,Niz+n,a,b);
ispisiniz(Niz,Niz+n);
cout<<endl;
long int t;
t=time(0);
sortniz2(Niz,Niz+n);
t=time(0)-t;
ispisiniz(Niz,Niz+n);
cout<<endl<<t;
getch();
return 0;
}

Ispis na ekranu:

Riješeni zadaci 2    Index