| Métodos de Ordenação/Classificação implementados em C# |
Selection Sort
Consiste
em localizar a posição do menor elemento e colocá-lo na posição i,
deste forma a cada iteração o início da coleção vai sendo ordenado.
public static void SelectionSort (int[] dados) {
for (int i = 0; i < dados.Length - 1; i++) {
int posMenor = i;
for (int j = i + 1; j < dados.Length; j++) {
if (dados[j] < dados[posMenor]) {
posMenor = j;
}
}
Troca(dados, i, posMenor);
}
} |
Método da Bolha
A
cada iteração o elemento é comparado com o seu sucessor e caso seja
maior, a posição dos dois são trocadas. A cada iteração o maior element
vai sendo deslocado para o final da coleção.
public static void BubbleSort (int[] dados) {
bool trocou;
int limite = dados.Length - 1;
do {
trocou = false;
for (int i = 0; i < limite; i++) {
if (dados[i] > dados[i + 1]) {
Troca(dados, i, i + 1);
trocou = true;
}
}
limite--;
} while (trocou);
} |
Inserção direta
Consiste
em selecionar a posição onde o elemento deve ser inserido mantendo a
coleção em ordem. As iterações iniciam a partir da segunda posição e os
elementos a esquerda são mantidos ordenados.
public static void InsertionSort (int[] dados) {
for (int i = 1; i < dados.Length; i++) {
int posNovo = i - 1;
int novoDado = dados[i];
while (posNovo >= 0 &&
novoDado < dados[posNovo]) {
dados[posNovo + 1] = dados[posNovo];
posNovo--;
}
dados[posNovo + 1] = novoDado;
}
}
|
QuickSort
Em construção
public static void QuickSort (int[] dados, int inicio, int fim) {
if (inicio < fim) {
int pivo = QuickSortPartition(dados, inicio, fim);
QuickSort(dados, inicio, pivo - 1);
QuickSort(dados, pivo + 1, fim);
}
}
public static int QuickSortPartition (int[] dados, int inicio, int fim) {
int pivo = inicio;
int esq = inicio;
int dir = fim;
while (esq < dir) {
while (esq < dir &&
dados[esq] <= dados[pivo]) {
esq++;
}
while (esq < dir &&
dados[dir] > dados[pivo]) {
dir--;
}
if (esq < dir) {
Troca(dados, esq, dir);
}
}
Troca(dados, pivo, dir);
return dir;
}
|
MergeSort
Em construção
public static void MergeSort (int[] dados, int inicio, int fim) {
if (inicio < fim - 1) {
int meio = (inicio + fim) / 2;
MergeSort (dados, inicio, meio);
MergeSort (dados, meio, fim);
MergeSortIntercala (dados, inicio, meio, fim);
}
}
public static void MergeSortIntercala (int[] dados, int inicio, int meio, int fim) {
int iEsq = inicio;
int iDir = meio;
int iAux = 0;
int[] dadosAux = new int[fim - inicio];
while (iEsq < meio && iDir < fim) {
if (dados[iEsq] < dados[iDir]) {
dadosAux[iAux++] = dados[iEsq++];
} else {
dadosAux[iAux++] = dados[iDir++];
}
}
while (iEsq < meio) {
dadosAux[iAux++] = dados[iEsq++];
}
while (iDir < fim) {
dadosAux[iAux++] = dados[iDir++];
}
iAux = 0;
while (iAux < dadosAux.Length) {
dados[inicio++] = dadosAux[iAux++];
}
}
|
HeapSort
Em construção
public static void MaxHeapify (int[] dados, int tam, int pos) {
int esq = 2 * pos + 1;
int dir = 2 * pos + 2;
int maior = pos;
if (esq < tam &&
dados[esq] > dados[pos]) {
maior = esq;
}
if (dir < tam &&
dados[dir] > dados[maior]) {
maior = dir;
}
if (maior != pos) {
Troca(dados, pos, maior);
MaxHeapify(dados, tam, maior);
}
}
public static void BuildMaxHeap (int[] dados, int tam) {
for (int i = dados.Length / 2; i >= 0; i--) {
MaxHeapify(dados, tam, i);
}
} public static void HeapSort (int[] dados) {
BuildMaxHeap(dados, dados.Length);
for (int i = dados.Length - 1; i > 0; i--) {
Troca(dados, 0, i);
MaxHeapify(dados, i, 0);
}
}
|
|