Welcome to BitCell. Click here to register !
), putem sari peste prezenta de la laboratoare, venind la examen cu un program a carui tema ne-o va da el. M-am oferit voluntar (mai mult pentru a evita sa ma arunce pe coridor 
) si mi-a dat, ca tema a programului, algoritmi de sortare. Trebuia sa ma prezint la examen cu un program care sa aiba implementati minim 4 algoritmi de sortare pentru o nota de trecere. Pentru nota 10 trebuia sa dau si explicatiile aferente 
... pacat ca acum nu mai inteleg chiar tot ce se intampla pe acolo, decat daca stau sa-mi chinui neuronul ...Programul l-am scris in Borland C++ 3.1 (you know, the DOS version
) si ofera un meniu interactiv (cu afisari direct in memoria video) care poate fi folosit cu sagetile sau cu mouse-ul, 7 algoritmi de sortare (initial erau doar 6) si doua metode de interschimbare.O imagine din timpul rularii programului:
Have fun
- /* CREATED : 17.11.2002
- MODIFIED : 05.03.2004 (added Shaker-Sort)
- ALGORITMI DE SORTARE
- --------------------
- Program care implementeaza mai multi algoritmi de sortare asupra unui
- vector de numere intregi. Au fost implementati algoritmii:
- 1. Bubble-Sort (metoda bulelor)
- 2. Quick-Sort (sortare rapida)
- 3. Sortare prin numarare
- 4. Sortare prin insertie
- 5. Shell-Sort (h-sortare)
- 6. Sortare prin interschimbare
- 7. Shaker-Sort
- Interschimbarea a doua numere a fost realizata in doua variante, una care
- presupune folosirea unei variabile auxiliare, iar cealalta folosind doar
- operatiile adunare si scadere
- by DarkByte */
- #include"conio.h"
- #include"dos.h"
- #include"stdio.h"
- #include"stdlib.h"
- #include"string.h"
- long int a[200];
- int n, metoda, metoda_sort;
- char i,b,Mouse=0, Buttons, Draw=0;
- unsigned MouseX=0, MouseY=0, MouseB=0;
- void init (void);
- void info (void);
- void meniu (void);
- void sortare_bule (long int sir[], int n);
- void sortare_quick (int i, int s, long int sir[]);
- void sortare_numarare (long int sir[], int n);
- void sortare_insertie (long int sir[], int n);
- void sortare_shell (long int sir[], int n);
- void sortare_intersch (long int sir[], int n);
- void sortare_shaker (long int sir[], int n);
- void Sortare_sir (long int sir[], int n, int metoda);
- void afisare_sir (long int sir[], int n);
- void swap (long int *a,long int *b, int metoda);
- void main(void)
- {
- textmode(C80);
- init();
- meniu();
- }
- void InitMouse(char *Inst, char *Buttons)
- {
- unsigned I;
- unsigned char B;
- asm {
- mov ax,0;
- int 0x33;
- mov I, ax;
- mov B, bl;
- }
- if (I == 0xFFFF) *Inst = 1;
- else *Inst = 0;
- *Buttons = B;
- }
- void ShowMouse(void)
- {
- asm {
- mov ax,1
- int 0x33;
- }
- }
- void HideMouse(void)
- {
- asm {
- mov ax,2
- int 0x33;
- }
- }
- void ReadMouse(char Gr)
- {
- unsigned int Bb, Xx, Yy;
- asm {
- mov ax, 3;
- int 0x33;
- mov Bb, bx;
- mov Xx, cx;
- mov Yy, dx;
- }
- if (Gr) {
- MouseB = Bb;
- MouseX = Xx;
- MouseY = Yy;
- }
- else {
- MouseB = Bb;
- MouseX = Xx / 8 + 1;
- MouseY = Yy / 8 + 1;
- }
- }
- void RestrictMouseX(unsigned X1, unsigned X2, char Gr)
- {
- if (!Gr) {
- X1 = X1 * 8 - 1;
- X2 = X2 * 8 - 1;
- }
- asm {
- mov ax, 7;
- mov cx, X1;
- mov dx, X2;
- int 0x33;
- }
- }
- void RestrictMouseY(unsigned Y1, unsigned Y2, char Gr)
- {
- if (!Gr) {
- Y1 = Y1 * 8 - 1;
- Y2 = Y2 * 8 - 1;
- }
- asm {
- mov ax, 8;
- mov cx, Y1;
- mov dx, Y2;
- int 0x33;
- }
- }
- void RestrictMouse(unsigned X1, unsigned Y1, unsigned X2, unsigned Y2, char Gr)
- {
- RestrictMouseX(X1,X2,Gr);
- RestrictMouseY(Y1,Y2,Gr);
- }
- void WriteAt(char X, char Y, char *N, char F, char B, char Col)
- {
- register int I,Pos;
- unsigned int far *VideoPtr;
- typedef struct {
- int bit_char : 8;
- int bit1_4 : 4;
- int bit5_7 : 3;
- int bit8 : 1;
- }bit_field;
- union VideoLocation {
- bit_field BF;
- unsigned a;
- }Video;
- VideoPtr = (unsigned int*) MK_FP (0xB800,0);
- Pos = Col*(Y-1)+(X-1);
- if (Draw) HideMouse();
- for (I=Pos;I<strlen(N)+Pos;I++){
- Video.BF.bit_char=N[I-Pos];
- Video.BF.bit1_4=F;
- Video.BF.bit5_7=B;
- Video.BF.bit8=0;
- VideoPtr[I] = Video.a;
- }
- if (Draw) ShowMouse();
- }
- void SetMouse(unsigned X, unsigned Y, char Gr)
- {
- if (!Gr) {
- X = X * 8 - 1;
- Y = Y * 8 - 1;
- }
- asm {
- mov ax,4;
- mov cx, X;
- mov dx, Y;
- int 0x33;
- }
- }
- void init(void)
- {
- n=5;
- a[0]=5;
- a[1]=1;
- a[2]=9;
- a[3]=3;
- a[4]=7;
- metoda_sort=1;
- metoda=1;
- }
- void info(char *s)
- {
- int i;
- char *met;
- WriteAt(10, 1 ,"Program de sortare a unui sir de maxim 200 de numere intregi", 14, 1, 80);
- WriteAt(3, 3 ,"Setarile ", 15, 0, 80);
- WriteAt(12, 3, s, 15, 0, 80);
- WriteAt(12 + strlen(s) + 1, 3, "ale acestui program sunt :", 15, 0, 80);
- WriteAt(5, 4, "- sirul de numere este ->", 15, 0, 80);
- gotoxy(31, 4);
- textattr(9);
- for (i=0; i<n; i++)
- printf("%d ",a[i]);
- WriteAt(5, 7, "- metoda de sortare este ", 15, 0, 80);
- switch (metoda_sort){
- case 1 : met = "Bubble-Sort."; break;
- case 2 : met = "Quick-Sort."; break;
- case 3 : met = "sortarea prin numarare."; break;
- case 4 : met = "sortarea prin insertie."; break;
- case 5 : met = "Shell-Sort."; break;
- case 6 : met = "sortarea prin interschimbare."; break;
- case 7 : met = "Shaker-sort";
- }
- WriteAt(30, 7, met, 14, 0, 80);
- WriteAt(5, 8, "- metoda de interschimbare este metoda ", 15, 0, 80);
- switch (metoda){
- case 1 : met = "standard."; break;
- case 2 : met = "aritmetica.";
- }
- WriteAt(44, 8, met, 14, 0, 80);
- }
- void clear(void)
- {
- int i, j;
- for (i=17; i<=25; i++)
- for (j=1; j<=80; j++)
- WriteAt(j, i, " ", 15, 0, 80);
- }
- void citire(long int sir[])
- {
- char c, *s;
- int i, j;
- clear();
- n=0;
- do{
- WriteAt(1,18,"Dati numarul de elemente al sirului:",14,0,80);
- gotoxy(39,18);
- _setcursortype(_NORMALCURSOR);
- gets(s);
- sscanf(s,"%d",&n);
- _setcursortype(_NOCURSOR);
- clear();
- } while ((n<1)||(n>200));
- for (i=0;i<n;i++){
- WriteAt(1,18,"Dati element: ",14,0,80);
- gotoxy(1,19);
- _setcursortype(_NORMALCURSOR);
- scanf("%d",&sir[i]);
- _setcursortype(_NOCURSOR);
- clear();
- gotoxy(1,21);
- for (j=0;j<=i;j++) printf("%d ",sir[j]);
- }
- clear();
- }
- int aleg_sort(void)
- {
- char c;
- clear();
- WriteAt(1,17,"CE SORTARE DORITI ?",14,0,80);
- WriteAt(1,18,"1. Bubble-Sort",15,0,80);
- WriteAt(1,19,"2. Quick-Sort",15,0,80);
- WriteAt(1,20,"3. Sortare prin numarare",15,0,80);
- WriteAt(1,21,"4. Sortare prin insertie",15,0,80);
- WriteAt(1,22,"5. Shell-Sort",15,0,80);
- WriteAt(1,23,"6. Sortare prin interschimbare",15,0,80);
- WriteAt(1,24,"7. Shaker-Sort",15,0,80);
- gotoxy(1,25);
- _setcursortype(_NORMALCURSOR);
- do{
- c=getch();
- }while ((c<'1')||(c>'7'));
- printf("%c",c);
- _setcursortype(_NOCURSOR);
- clear();
- return c;
- }
- int aleg_met(void)
- {
- char c;
- clear();
- WriteAt(1,17,"Ce metoda de interschimbare doriti?",14,0,80);
- WriteAt(1,18,"1. Standard (cu folosire auxiliar)",15,0,80);
- WriteAt(1,19,"2. Aritmetica (fara folosire auxiliar)",15,0,80);
- gotoxy(1,20);
- _setcursortype(_NORMALCURSOR);
- do{
- c=getch();
- }while ((c<'1')||(c>'2'));
- printf("%c",c);
- _setcursortype(_NOCURSOR);
- clear();
- return c;
- }
- char *optiune ( int i )
- {
- char *o;
- switch (i) {
- case 1:o=" Citire sir ";break;
- case 2:o=" Alegerea algoritmului de sortare ";break;
- case 3:o="Alegerea metodei de interschimbare";break;
- case 4:o=" SORTEAZA ! ";break;
- case 5:o=" Afiseaza sir ";break;
- case 6:o=" Iesire din program ";
- }
- return o;
- }
- void chenar(int x, int y)
- {
- int i;
- for (i=0;i<=33;i++) {
- WriteAt(x+i,y,"Ä",15,0,80);
- WriteAt(x+i,y+7,"Ä",15,0,80);
- }
- for (i=1;i<=6;i++) {
- WriteAt(x-1,y+i,"³",15,0,80);
- WriteAt(x+34,y+i,"³",15,0,80);
- }
- WriteAt(x-1,y,"Ú",15,0,80);
- WriteAt(x+34,y,"¿",15,0,80);
- WriteAt(x-1,y+7,"À",15,0,80);
- WriteAt(x+34,y+7,"Ù",15,0,80);
- }
- int GetOpt(int y)
- {
- return MouseY-y;
- }
- void Restore_Image(int indent, int top, int o)
- {
- textbackground(0);
- HideMouse();
- clrscr();
- _setcursortype(_NOCURSOR);
- for (i=1;i<=6;i++)
- WriteAt(indent,top+i,optiune(i),8,0,80);
- WriteAt(indent,top+o,optiune(o),14,1,80);
- chenar(indent,top);
- info("actuale");
- ShowMouse();
- }
- void close(void)
- {
- RestrictMouse(1, 1, 80, 25, 0);
- exit(0);
- }
- void meniu(void)
- {
- int opt=1,indent=25,top=9;
- char c;
- textbackground(0);
- clrscr();
- _setcursortype(_NOCURSOR);
- WriteAt(indent,top+1,optiune(1),14,1,80);
- for (i=2;i<=6;i++)
- WriteAt(indent,top+i,optiune(i),8,0,80);
- chenar(indent,top);
- info("implicite");
- InitMouse(&Mouse, &Buttons);
- Draw = 1;
- RestrictMouse(indent, top+1,indent+33, top + 6, 0);
- ShowMouse();
- do {
- ReadMouse(0);
- if (kbhit()!=0) {
- c=getch();
- switch(c){
- case 0:c=getch();
- switch(c){
- case 72:WriteAt(indent,top+opt,optiune(opt),8,0,80);
- opt--;
- if (opt==0) opt=6;
- WriteAt(indent,top+opt,optiune(opt),14,1,80);
- break;
- case 80:WriteAt(indent,top+opt,optiune(opt),8,0,80);
- opt++;
- if (opt==7) opt=1;
- WriteAt(indent,top+opt,optiune(opt),14,1,80);
- };break;
- case 13:switch (opt){
- case 1:citire(a);Restore_Image(indent,top,opt);break;
- case 2:metoda_sort=aleg_sort()-48;Restore_Image(indent,top,opt);break;
- case 3:metoda=aleg_met()-48;Restore_Image(indent,top,opt);break;
- case 4:Sortare_sir(a,n,metoda_sort);
- case 5:afisare_sir(a,n);clear();Restore_Image(indent,top,opt);break;
- case 6:close();
- };
- }
- }
- else {
- if (MouseB==1) {
- i=GetOpt(top);
- if (i!=opt) {
- WriteAt(indent,top+opt,optiune(opt),8,0,80);
- opt=i;
- WriteAt(indent,top+opt,optiune(opt),14,1,80);
- delay(200);
- }
- else switch (opt){
- case 1:citire(a);Restore_Image(indent,top,opt);break;
- case 2:metoda_sort=aleg_sort()-48;Restore_Image(indent,top,opt);break;
- case 3:metoda=aleg_met()-48;Restore_Image(indent,top,opt);break;
- case 4:Sortare_sir(a,n,metoda_sort);
- case 5:afisare_sir(a,n);clear();Restore_Image(indent,top,opt);break;
- case 6:close();
- };
- }
- }
- }while (c!=27);
- }
- void sortare_bule(long int sir[], int n)
- {
- register int i,j;
- char gata;
- do{
- gata=1;
- for (i=0;i<n;i++)
- if (sir[i]>sir[i+1]) {
- swap(&sir[i],&sir[i+1],metoda);
- gata=0;
- }
- n--;
- }while (!gata);
- }
- void sortare_quick(int i, int s, long int sir[])
- {
- long int el;
- register int st,dr;
- st=i;
- dr=s;
- el=sir[(st+dr)/2];
- do{
- while (sir[st]<el) st++;
- while (el<sir[dr]) dr--;
- if (st<=dr) {
- if (sir[st]!=sir[dr]) swap(&sir[st],&sir[dr],metoda);
- st++;
- dr--;
- }
- }while (!(dr<=st));
- if (i < dr) sortare_quick(i,dr,sir);
- if (st < s) sortare_quick(st,s,sir);
- }
- void sortare_numarare(long int sir[], int n)
- {
- long int s1[500];
- register int i,j;
- int c;
- for (i=0;i<=500;i++) s1[i]=0;
- for (i=0;i<=n;i++) {
- c=0;
- for (j=0;j<=n;j++)
- if (sir[j]<sir[i]) c++;
- while (s1[c]) c++;
- s1[c]=sir[i];
- }
- for (i=0;i<=n;i++) sir[i]=s1[i];
- }
- void sortare_insertie(long int sir[], int n)
- {
- long int s1[500];
- register int i,j;
- int k,aux;
- char gata;
- for (i=1;i<=n;i++){
- aux=sir[i];
- k=-1;
- j=i-1;
- gata=0;
- while ((j>=0)&&(!gata)){
- if (sir[j]>aux){
- sir[j+1]=sir[j];
- j--;
- }
- else{
- k=j;
- gata=1;
- };
- }
- sir[k+1]=aux;
- }
- }
- void sortare_shell(long int sir[], int n)
- {
- int i,h;
- char gata;
- h=n;
- while (h>1) {
- h=h / 2;
- do {
- gata=1;
- for (i=0;i<=n-h;i++) {
- if (sir[i]>sir[i+h]) {
- swap(&sir[i],&sir[i+h],metoda);
- gata=0;
- }
- };
- }while (!gata);
- }
- }
- void sortare_interschimbare(long int sir[], int n)
- {
- register int i,j;
- for (i=0;i<=n;i++)
- for (j=i+1;j<=n;j++)
- if (sir[i]>sir[j]) {
- swap(&sir[i],&sir[j],metoda);
- }
- }
- void sortare_shaker(long int sir[], int n)
- {
- register int j;
- int k,s,d;
- s=1;
- k=n;
- d=n;
- do {
- for (j=d;j>=s;j--)
- if (sir[j-1]>sir[j]) {
- swap(&sir[j-1],&sir[j],metoda);
- k=j;
- }
- s=k+1;
- for (j=s;j<=d;j++)
- if (sir[j-1]>sir[j]) {
- swap(&sir[j-1],&sir[j],metoda);
- k=j;
- }
- d=k-1;
- } while (s<=d);
- }
- void afisare_sir(long int sir[], int n)
- {
- int i,b,x,y;
- clear();
- gotoxy(1,18);
- if (n)
- for (i=0;i<n;i++)
- printf("%d ",sir[i]);
- else printf("Nu a fost introdus sirul !");
- WriteAt(60,25,"Apasati orice tasta !",15,0,80);
- getch();
- }
- void Sortare_sir(long int sir[], int n, int metoda)
- {
- switch (metoda) {
- case 1:sortare_bule(sir,n-1);
- break;
- case 2:sortare_quick(0,n-1,sir);
- break;
- case 3:sortare_numarare(sir,n-1);
- break;
- case 4:sortare_insertie(sir,n-1);
- break;
- case 5:sortare_shell(sir,n-1);
- break;
- case 6:sortare_interschimbare(sir,n-1);
- break;
- case 7:sortare_shaker(sir,n-1);
- }
- }
- void swap(long int *v1, long int *v2, int metoda)
- {
- long int aux;
- switch (metoda){
- case 1: aux=*v1;
- *v1=*v2;
- *v2=aux;
- break;
- case 2: *v1=*v1+*v2;
- *v2=*v1-*v2;
- *v1=*v1-*v2;
- }
- }
- /*
- MUST STILL BE DONE !!!
- *alegere tip de sortare - ascendenta, descendenta
- */
