- 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.
- 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).
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;
}
}
}
}
- 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.
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;
}
}
- 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).
- 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.
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++;
}
}
- 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].
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;
}