lab4

//Alexe Tudor Stefan:)
/*1.Implementaţi metoda bulelor (Bubble-Sort) care foloseşte un indicator flag. Se cere atât scrierea funcţiei, cât şi
partea de program care face citirea şi afişarea şirului iniţial şi a celui ordonat.*/
#include<stdio.h>
void SortBubble(int *p, int n);
int main(void)
{
int n,*p;
printf("Introduceti numarul de elemente ce urmeaza a fi citite:");scanf("%d",&n);
p=new int[n];
for(int i=0;i<n;i++)
{
printf("Introduceti p[%d]=",i);scanf("%d",&p[i]);
}
SortBubble(p,n);
printf("Sirul sortat este:\n");
for(int i=0;i<n;i++)
{
printf("%d ",p[i]);
}
delete p;
}
void SortBubble(int *p, int n)
{
int i, j, temp, flag;
for(i=1; i<n; i++)
{
flag = 0;
for(j=n-1; j>=i; j--)
{
if(p[j-1] > p[j])
{
// intershimbare
temp = p[j];
p[j] = p[j-1];
p[j-1] = temp;
flag = 1;
}
}
// daca nu s-a facut nici o interschimbare
if(flag == 0)
break;
}
}

/* 2.Modificaţi programul care exemplifică metoda de sortare grabnică (Quick-Sort) aşa încât să ordoneze şirul iniţial
în ordine descrescătoare.*/

#include<stdio.h>
void QuickSort(int *p, int prim, int ultim);
int main(void)
{
int n,*p;
printf("Introduceti numarul de elemente ce urmeaza a fi citite:");scanf("%d",&n);
p=new int[n];
for(int i=0;i<n;i++)
{
printf("Introduceti p[%d]=",i);scanf("%d",&p[i]);
}
QuickSort(p,0,n-1);
printf("Sirul sortat este:\n");
for(int i=0;i<n;i++)
{
printf("%d ",p[i]);
}
delete p;
}
void QuickSort(int *p, int prim, int ultim)
{
int i, j, pivot, temp;
i = prim;
j = ultim;
pivot = p[ultim];
// partitionare
do
{
while(p[i] > pivot)
i++;
while(p[j] < pivot)
j--;
if(i < j)
{
temp = p[i];
p[i] = p[j];
p[j] = temp;
}//end if
if(i <= j)
{
j--;
i++;
}//end if
}
while(i < j);//end do-while
// apel recursiv
if(prim < j)
QuickSort(p, prim, j);
if(i < ultim)
QuickSort(p, i, ultim);
}//end QuickSort

/* 3.Folosiţi funcţiile de bibliotecă pentru sortări (qsort) pentru a aranja un şir de înregistrări cu nume, prenume,
cod numeric personal, data angajării după două câmpuri la alegere (un exemplu ar fi: crescător după nume şi
descrescător pe urmă data angajării).*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct data
{
int zi;
int luna;
int an;
};
struct angajat
{
char nume[256];
char prenume[256];
int cnp;
struct data data_angajarii;
};
int sort_way=1;
struct angajat *read(int n);
int comparare(struct angajat *v1,struct angajat *v2);
char *data_to_char(struct data *date);
void afis_pers(struct angajat *pers);
int main(void)
{
int n;
struct angajat *pers;
printf("Bine ati venit!\nIntroduceti cate persoane doriti sa introduceti in Baza de date: ");scanf("%d",&n);
pers=read(n);
//printf("Pentru o sortare alfabetica tastati 1, iar pentru o sortare alfabetic inversa tastati -1: ");scanf("%d",&sort_way);
if((sort_way!=1)&&(sort_way!=-1))
{
printf("Optiunea introdusa nu exista.Se va realiza o sortare alfabetic crescatoare\n");
sort_way=1;
}
//qsort( (struct angajat *)pers, n, sizeof( struct angajat ), (int (*) (const void *, const void *)) comparare );
printf("Dupa sortare, ființele se prezinta astfel:\n");
for(int i=0;i<n;i++)
{
printf("Persoana %d:\n",i+1);
afis_pers(&pers[i]);
}
return 0;
}
struct angajat *read(int n)
{
struct angajat *pers=new struct angajat[n];
char tmp[11],zi[3],luna[3],an[4];
for(int i=0;i<n;i++)
{
printf("Introduceti datele pentru persoana %d:\n",i+1);
printf("Nume: ");scanf("%s",pers[i].nume);
printf("Prenume: ");scanf("%s",pers[i].prenume);
printf("Cnp: ");scanf("%d",&pers[i].cnp);
printf("Data angajarii(zz/ll/aaaa): ");scanf("%s",tmp);
if((strlen(tmp)!=10)||(tmp[2]!='/')||(tmp[5]!='/'))
{
printf("Formatul datei angajarii este incorect. Va rugam introduceti dinou datele pentru angajatul %d",i+1);
i--;
continue;
}
//printf("nu se continua");
zi[0]=tmp[0];
zi[1]=tmp[1];
zi[2]='\0';
luna[0]=tmp[3];
luna[1]=tmp[4];
luna[2]='\0';
an[0]=tmp[6];
an[1]=tmp[7];
an[2]=tmp[8];
an[3]=tmp[9];
an[4]='\0';
pers[i].data_angajarii.zi=atoi(zi);
pers[i].data_angajarii.luna=atoi(luna);
pers[i].data_angajarii.an=atoi(an);
}
return pers;
}
int comparare(struct angajat *v1,struct angajat *v2)
{
char str1[256]="",str2[256]="";
int rez;
strcpy(str1,v1->nume);
strcat(str1,v1->prenume);
strcpy(str2,v1->nume);
strcat(str2,v1->prenume);
rez=strcmp(str1,str2);
if(rez!=0) return sort_way*rez;
else return sort_way*strcmp(data_to_char(&v1->data_angajarii),data_to_char(&v2->data_angajarii));
}
char *data_to_char(struct data *date)
{
char *string=new char[9];
string[0]=(date->an)%10000+48;
string[1]=(date->an)%1000+48;
string[2]=(date->an)%100+48;
string[3]=(date->an)%10+48;
string[4]=(date->luna)%100+48;
string[5]=(date->luna)%10+48;
string[6]=(date->zi)%100+48;
string[7]=(date->zi)%10+48;
string[8]='\0';
return string;
}
void afis_pers(struct angajat *pers)
{
printf("Nume: %s\n",pers->nume);
printf("Prenume: %s\n",pers->prenume);
printf("Cnp: %d\n",pers->cnp);
printf("Data angajarii: %d/%d/%d\n",pers->data_angajarii.zi,pers->data_angajarii.luna,pers->data_angajarii.an);
}

/* 4. Scrieţi o aplicaţie C/C++ in care plecând de la două şiruri de numere naturale să se obţină un al treilea şir care
să conţină toate elementele şirurilor sursă fără a se repeta, aranjate în ordine crescătoare.*/

#include<stdio.h>
#include<stdlib.h>
int comparare(int *v1,int *v2);
int main(void)
{
int n,m,*sir1,*sir2,*sir3,i=0,j=0,k=0;
printf("Introduceti mărimea primului sir de numere naturale: ");scanf("%d",&n);
printf("Introduceti măsură celui de-al doilea sir de numere naturale: ");scanf("%d",&m);
sir1=new int[n];
sir2=new int[m];
sir3=new int[m+n];
for(int i=0;i<n;i++)
{
printf("sir1[%d]= ",i);scanf("%d",&sir1[i]);
}
for(int i=0;i<m;i++)
{
printf("sir1[%d]= ",i);scanf("%d",&sir2[i]);
}
qsort( (int *)sir1, n, sizeof( int ), (int (*) (const void *, const void *)) comparare );
qsort( (int *)sir2, n, sizeof( int ), (int (*) (const void *, const void *)) comparare );
while(i+j<m+n+1)
{
if(sir1[i]<sir2[j])
{
if(i<n) sir3[k++]=sir1[i++];
else sir3[k++]=sir2[j++];
}
else
{
if(j<m) sir3[k++]=sir2[j++];
else sir3[k++]=sir1[i++];
}
if(k-1) if(sir3[k-1]==sir3[k-2]) k--;
}
printf("Sir3: ");
for(int i=0;i<k-1;i++)
{
printf("%d, ",sir3[i]);
}
}
int comparare(int *v1,int *v2)
{
return *v1-*v2;
}

/* 5.Completati codul ultimei probleme date ca exemplu cu alte metode de sortare (sortarea prin selectie, sortarea
shell, etc.). Cititi de la tastatura numarul de elemente al sirurilor de valori si apoi trimiteti-l ca parametru la
fiecare functie. Comparati timpii de fapt ai fiecarui algoritm.*/

#include<stdio.h>
#include<stdlib.h>
void SortIns(int *p, int n);
void SortSel(int *p, int n);
void SortBoubble(int *p, int n);
void QuickSort(int *p, int prim, int ultim);
int comparare( const void *arg1, const void *arg2 );
int main(void)
{
int n,*p;
printf("Introduceti numarul de elemente ce urmeaza a fi citite:");scanf("%d",&n);
p=new int[n];
for(int i=0;i<n;i++)
{
printf("Introduceti p[%d]=",i);scanf("%d",&p[i]);
}
//SortBoubble(p,n);
//QuickSort(p,0,n-1);
//SortSel(p,n);
//SortIns(p,n);
qsort( (int*)p, n, sizeof( int ), comparare );
printf("Sirul sortat este:\n");
for(int i=0;i<n;i++)
{
printf("%d ",p[i]);
}
delete p;
}
void SortBoubble(int *p, int n)
{
int i, j, temp;
for(i=1; i<n; i++)
{
for(j=n-1; j>=i; j--)
{
if(p[j-1] < p[j])
{
temp = p[j];
p[j] = p[j-1];
p[j-1] = temp;
}//end if
}//end for
}//end for
}//end SortBubble()
void SortSel(int *p, int n)
{
int i, j, pozmin, temp;
for(i=0; i<n; i++)
{
// cautare pozitie cel mai mic element din sirul curent
pozmin = i;
for(j=i+1; j<n; j++)
{
if(p[pozmin] < p[j])
pozmin = j;
}//end for
// interschimbare cu elementul de pe întâia pozitie
temp = p[pozmin];
p[pozmin] = p[i];
p[i] = temp;
}//end for
}//end SortSel

void QuickSort(int *p, int prim, int ultim)
{
int i, j, pivot, temp;
i = prim;
j = ultim;
pivot = p[ultim];
// partitionare
do
{
while(p[i] > pivot)
i++;
while(p[j] < pivot)
j--;
if(i < j)
{
temp = p[i];
p[i] = p[j];
p[j] = temp;
}//end if
if(i <= j)
{
j--;
i++;
}//end if
}
while(i < j);//end do-while
// apel recursiv
if(prim < j)
QuickSort(p, prim, j);
if(i < ultim)
QuickSort(p, i, ultim);
}//end QuickSort
void SortIns(int *p, int n)
{
int i, j, temp;
for(i=1; i<n; i++)
{
temp = p[i];
for(j=i-1; j>=0; j--)
{
if(p[j] < temp)
p[j+1] = p[j];
else
break;
}//end for
p[j+1] = temp;
}//end for
}//end SortIns()
int comparare( const void *arg1, const void *arg2 )
{
if(*(int *)arg1<*(int *)arg2)
return 1;
if(*(int *)arg1==*(int *)arg2)
return 0;
if(*(int *)arg1>*(int *)arg2)
return -1;
}

/* 6.Cititi de la tastatura m elemente de tip intreg intr-un vector si o valoare intreaga n<m. Impartiti sirul citit in
doua subsiruri astfel:
a) inițialul subsir va contine primele n elemente din sirul initial
b) al doilea subsir va contine restul elementelor din sirul initial.
Sa se realizeze urmatoarele operatii:
1. sa se ordoneze crescator cele doua subsiruri
2. sa se sorteze sirul initial, prin interclasarea celor doua subsirui ordonate. (merge-sort)*/

#include<stdio.h>
#include<stdlib.h>
int comparare(int *v1,int *v2);
int main(void)
{
int m,n=0,*sir,*sir1,*sir2;
printf("Introduceti numarul de elemente ale sirului initial: ");scanf("%d",&m);
sir=new int[m];
for(int i=0;i<m;i++)
{
printf("Introduceti sir[%d]: ",i+1);scanf("%d",&sir[i]);
}
while(!n)
{
printf("Introduceti un numar n<%d: ",m);scanf("%d",&n);
if(!(n<m))
{
printf("Numarul introdus nu este mai mic ca si %d: ",m);
n=0;
}
}
sir1=new int[n];
sir2=new int[m-n];
for(int i=0;i<n;i++)
{
sir1[i]=sir[i];
}
for(int i=m-n,j=0;i<m;i++)
{
sir2[j]=sir[i];
}
int i=0,j=0,k=0;
qsort( (int *)sir1, n, sizeof( int ), (int (*) (const void *, const void *)) comparare );
qsort( (int *)sir2, m-n, sizeof( int ), (int (*) (const void *, const void *)) comparare );
while(i+j<m+1)
{
if(sir1[i]<sir2[j])
{
if(i<n) sir[k++]=sir1[i++];
else sir[k++]=sir2[j++];
}
else
{
if(j<m-n) sir[k++]=sir2[j++];
else sir[k++]=sir1[i++];
}
if(k-1) if(sir[k-1]==sir[k-2]) k--;
}
printf("Sirul interclasat este: ");
for(int i=0;i<k-1;i++)
{
printf("%d, ",sir[i]);
}
return 0;
}
int comparare(int *v1,int *v2)
{
return *v1-*v2;
}

_________________
Detinator MiniZone
www.zappdivercity.blogspot.com