Quick_Sort

[+skyler_sdf]

1. Quick sort

Ordonarea Quick-sort este celebra si este una dintre metodele performante de sortare. Ideea algoritmului este simpla: in vectorul cu capetele inf si sup alegem un element (numit pivot) si apoi rearanjam elementele vectorului astfel incat in stanga sa se grupeze elemente mai mici sau egale cu pivotul, iar la dreapta elemente mai mari decat pivotul. In implementare vom alege ca pivot primul element al tabloului, apoi vom folosi doua variabile contor i si j cu care ne vom deplasa spre dreapta, respectiv stanga. Apoi amplasam pivotul pe pozitia dintre cei doi subvectori care se deplaseaza(unul cu elemente mai mici sau egale, unul cu elemente mai mari) si apelam quick_sort pentru acestia.

Procesul recursiv se executa doar daca cele doua limite sunt diferite(subproblema de baza este cea in care dimensiunea vectorului este 1).

#include<iostream.h>

#include<conio.h>

int a[20], n;

void quick_sort(int *a, int inf, int sup) 

{


	if(inf<sup)

	{

                                    int pivot=a[inf]; 

 		int aux;

		int i=inf+1, j=sup;


                                    while(i<=j)

		{


			while(i<=sup && a[i]<=pivot)

				i++;

			while(j>=inf && a[j]>pivot)

				j--;

			if(i<j && i<=sup && j>=inf)

			{


				aux=a[i];

				a[i]=a[j];

				a[j]=aux;

			}

		}

		i--;

		a[inf]=a[i];

		a[i]=pivot; 

		quick_sort(a, inf, i-1); 

		quick_sort(a, i+1, pivot);

	}

}

void afisare()

{


	int i;

	cout<<"vectorul sortat este: ";

	for(i=0; i<n; i++)

		cout<<a[i]<<" ";

}

void main()

{

  int i;

	cout<<"n=";

	cin>>n;

	for(i=0; i<n; i++)

	{


		cout<<"a["<<i<<"]="; cin>>a[i];

	}

	quick_sort(a, 0, n-1);

	afisare();

	getch();

}