/*   Sortarea rapida folosind metoda DIVIDE & IMPERA
      Se considera un vector a de dimensiune n. Sa se sorteze crescator
      vectorul
  - Pentru rezolvare este necesara o functie poz , care trateaza o portiune
  din vectorul dat cuprinsa intre indicii li (limita inferioara) si ls
  (limita superioara). Rolul acestei functii este de a pozitiona elementul
  a[li] pe o pozitie k cuprinsa intre li si ls, a.i. toate componentele
  vectorului cuprinse intre li si k-a sa fie mai mici sau egale cu a[k]
	si toate componentele cuprinse intre k+1 si ls sa fie mai mari sau egale
	cu a[k].
  In aceasta functie se vor utiliza 2 moduri de lucru:
  modul a) i ramane constant si j scade cu 1
  modul b) i creste cu 1 si j ramane constant
  Functia contine urmatoarele etape:
  	- i=li, j=ls
    - se trece la modul de lucru a)
    - atata timp cat (i<j) executa
					- daca a[i]>a[j] atunci se inverseaza cele 2 elemente si
																			se schimba modul de lucru
    			- i si j se modifica corespunzator modului de lucru curent
    - k ia valoarea comuna lui i si j
  Se mai utilizeaza si functia quick care implementeaza strategia
	tehnicii D&I
  obs. Elementul care initial a fost pe pozitia li si a ajuns pe k,
  va ramane pe acea pozitie in cadrul vectorului sortat (esenta alg.!!)
*/
#include <stdio.h>
#include <conio.h>
int a[100],n,k;
void poz(int li, int ls, int &k, int a[100])
	{
  	int i,j,aux,i1,j1;
    i=li;j=ls;i1=0;j1=-1;
    while (i<j)
    	{
	    if (a[i]>a[j])
	    	{ aux=a[j];
  	      a[j]=a[i];
	        a[i]=aux;
          //se seteaza i1, j1 pentru schimbarea modului de lucru
          aux=i1;
          i1=-j1;
          j1=-aux;
      	}
      i=i+i1;
      j=j+j1;
  		}
      k=i;
  }

void quick(int li, int ls)
	{
	  if (li<ls)
			{ poz(li,ls,k,a);
       	quick(li,k-1);
        quick(k+1,ls);
      }
  }

void main(void)
{
 clrscr();
 int i;
 printf("nr elemente pentru a =");scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
   printf("a[%d]=",i);scanf("%d",&a[i]);
 }
 quick(1,n);
 for(i=1;i<=n;i++)
   printf("%d\t",a[i]);
 printf("\n");
 getch();
 }