MergeSort

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

/*Abaixo do programa explico o uso da função sort, que pertence à biblioteca 'algorithm'*/
#include <iostream>
using namespace std;
#define N 10
void imprime (int a[])
{
	for (int i=0;i<N;i++)
		cout << a[i] << " ";
	cout << endl;
}
void Merge(int a[], int esq, int p, int dir)
{
	//criar um arranjo auxiliar 'L' contendo os elementos a[esq..p]
	int *l=new int[p-esq+1];
	for (int i=esq,j=0;i<=p;i++,j++)
		l[j]=a[i];
	
	//criar um arranjo auxiliar 'R' contendo os elementos a[p+1..dir]
	int *r=new int[dir-p+1];
	for (int i=p+1,j=0;i<=dir;i++,j++)
		r[j]=a[i];
	
	int i=0,j=0;
	
	for (int k=esq;k<=dir;k++){
		if (l[i]<=r[j]){
			a[k]=l[i];
			i++;
		}
		else {
			a[k]=r[j];
			j++;
		}
		
		if (i==p-esq+1){
			k++;
			while (j<=dir-p-1 ){
				a[k]=r[j];
				j++;
				k++;
			}
		}
		
		else if (j==dir-p){
			k++;
			while (i<=p-esq){
				a[k]=l[i];
				i++;
				k++;
			}
		}
		
		
	}
	delete[](r); delete[](l);
}
void MergeSort(int a[], int esq, int dir)
{
	if (esq<dir) {
		int p = (esq+dir)/2;
		MergeSort(a,esq,p);
		MergeSort(a,p+1,dir);
		Merge(a,esq,p,dir);
	}
}
int main (){
	
	int a[N];
	
	for (int i=0;i<10;i++)
		cin >> a[i];
	
	cout << "Arranjo:\n";
	imprime(a);
	
	MergeSort(a,0,9);
	
	cout << "Arranjo ordenado:\n";
	imprime(a);
	
	return 0;
}
/*Há também uma função da biblioteca 'algorithm' que realiza 
 a ordenação dos elementos de maneira eficiente, que se chama sort, se implementa da seguinte forma:*/
 
 #include <iostream>
 #include <algorithm> //biblioteca da função sort
 using namespace std;
 
 int main (){
	 
	 int v[10]={2, 21, 1, 32, 10, 12, 331, 0, 6, 3};
	 
	 int n=10;
	 
	 sort(v, v+n);//v->inicio do array, v+n, fim do array que tem n elementos;
	 
	 /*A função sort não é estável, então caso o problema necessite que os elementos 
	 não percam sua ordem caso sejam iguais, se usa a função stable_sort, que tem a notação idêntica à da sort*/
	 
	 stable_sort(v, v+n);
	 
	 for (int i=0; i<n; i++)
		cout << v[i] << " ";
	 cout << endl;
	 
	return 0;
}