ordenação_EDA_2017.1.md

Ordenação

• Em ciência da computação o algoritmo de ordenação é responsável por colocar certos elementos numa determinada ordem.
• A ordenação é considerado o problema mais fundamental do estudo de algoritmos.

Bubble Sort

• Mais simples dos algortmos de ordenação.
• Percorre o vetor, a ser ordenado, várias vezes e a cada passagem faz "flutuar para o topo" o maior elemento da sequência.
• Na maioria dos casos são feitas n² operações (comparações e trocas), ou seja, o algoritmo possui complexidade O(n²) (n representa a quantidade de elementos num vetor).
• Existe uma implementação na qual o melhor caso tem complexidade O(n).

Código

static void BubbleSort(int vetor[], int n);

void BubbleSort(int vetor[], int n)
{
	int i, j, swap;
	for(i=n-1; i>0; i--){
		for(j=0; j<i; j++){
			if(vetor[] > vetor[j+1]){
				swap=vetor[j];
				vetor[j]=vetor[j+1];
				vetor[j+1]=swap;
			}
		}
	}
}

Insertion Sort

• Eficiente para ordenação com poucos elementos.
• Complexidade O(n²) (n representa a quantidade de elementos num vetor) no pior e médio caso e O(n) no melhor, no entanto, é um algoritmo melhor que o Bubble Sort.

Código

static void InsertionSort(int vetor[], int n);

void InsertionSort(int vetor[], int n)
{
	int i, j, swap;
	for(i=1; i<n; i++){
		swap = vetor[i]
		for(j=i-1; j>=0 && vetor[j]>swap; j--){
			vetor[j+1]=vetor[j];
		}
		vetor[j+1]=swap;
	}
}

Merge Sort

• Algoritmo do tipo dividir-para-conquistar.
• Complexidade O(n*log n) (n representa a quantidade de elementos num vetor) no médio e pior caso.
• Necessida de memória, pois duplica elementos.
• Pouco eficiente na manipulação de grandes dados (devido ao processo de duplicar elementos e sua recursividade).

Ideia Básica

• Dividir: dividir os dados em subsequências pequenas;
• Conquistar: classidficar as duas metades recrusivamente aplicando o merge sort;
• Combinar: juntar as duas metades em um único conjunto já classificado.

Código

static void MergeSort(int vetor[], int l, int r);
static void Merge(int vetor[], int l, int m, int r);

void MergeSort(int vetor[], int l, int r)
{
	//Na primeira chamada da função r=quantidade de elementos-1 e l=0
	int m;
	if(l<r){
		m=l+(r-l)/2;
		
		MergeSort(vetor, l, m);
		MergeSort(vetor, m+1, r);
		
		Merge(vetor, l, m, r);
	}
}
void Merge(int vetor[], int l, int m, int r)
{
	int i, j, k;
	int n1=m-l+1;
	int n2=r-m;
	
	int l[n1], r[n2];

	for(i=0; i<n1; i++)
		l[i]=vetor[l+i];
	for(j=0; j<n2; j++)
		r[j]=vetor[m+1+j];

	i=0;
	j=0;
	k=l;
	while(i<n1 && j<n2){
		if(l[i]<=r[j]){
			vetor[k]=l[i];
			i++;
		}
		else{
			vetor[k]=r[j];
			j++;
		}
		k++;
	}
	
	while(j<n2){
		vetor[k]=r[j];
		j++;
		k++;
	}
}

Quick Sort

• Algoritmo do tipo dividir-para-conquistar.
• Complexidade O(n²) (n representa a quantidade de elementos num vetor) no pior caso, O(n*log n) no caso médio e melhor.
• O vetor[l...h] é particionado em dois subvetores não vazios, vetor[l...p-1] e vetor[p+1...r]. Garantindo que os elementos no vetor[l...p-1] são menores que todos elementos em vetor[p+1...h].

Código

static void QuickSort(int vetor[], int low, int high);
static int partition(int vetor[], int low, int high);

void QuickSort(int vetor[], int low, int high)
{
	int pi;
	if(low<high){
		pi=partition(vetor, low, high);
		
		QuickSort(vetor, low, pi-1);
		QuickSort(vetor, pi+1, high);
	}
}
int partition(int vetor[], int low, int high)
{
	int pivot=vetor[high], swap;
	int i=low-1, j;
	
	for(j=low; j<high; j++){
		if(vetor[j]<=pivot){
			i++;
			swap=vetor[i];
			vetor[i]=vetor[j];
			vetor[j]=swap;
		}
	}
	swap=vetor[i+1];
	vetor[i+1]=vetor[high];
	vetor[high]=swap;
	return i+1;
}

Heap Sort