A Ordenação por Mesclagem é um algoritmo de ordenação eficiente e estável que segue o paradigma de "dividir para conquistar". Ele divide recursivamente a lista em sublistas menores até que cada sublista contenha apenas um elemento (que está trivialmente ordenado). Em seguida, mescla essas sublistas ordenadas para produzir uma lista final ordenada.
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> leftArr(n1);
std::vector<int> rightArr(n2);
for (int i = 0; i < n1; ++i)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i++];
} else {
arr[k] = rightArr[j++];
}
k++;
}
while (i < n1) {
arr[k++] = leftArr[i++];
}
while (j < n2) {
arr[k++] = rightArr[j++];
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main() {
int n;
std::cin >> n;
std::vector<int> data(n);
for (int i = 0; i < n; ++i) {
std::cin >> data[i];
}
mergeSort(data, 0, n - 1);
for (int i = 0; i < n; ++i) {
std::cout << data[i] << ' ';
}
std::cout << std::endl;
return 0;
}
A Ordenação Rápida é um algoritmo de ordenação divide-and-conquer. Ele seleciona um 'pivô' da matriz e particiona os outros elementos em duas submatrizes, de acordo com se eles são menores ou maiores que o pivô. Em seguida, ordena recursivamente as submatrizes. Sua eficiência em média o torna popular, embora o pior caso possa ser ruim.
#include <algorithm> // Para std::swap
#include <vector>
void quickSort(std::vector<int>& arr, int low, int high) {
if (low >= high) {
return;
}
// Escolhe um pivô (ex: elemento do meio)
int pivotValue = arr[low + (high - low) / 2];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivotValue);
do {
j--;
} while (arr[j] > pivotValue);
if (i >= j) {
break; // Partição completa
}
std::swap(arr[i], arr[j]);
}
// Chamadas recursivas para as submatrizes
quickSort(arr, low, j);
quickSort(arr, j + 1, high);
}
A Ordenação por Heap é um algoritmo de comparação de ordenação baseado na estrutura de dados Heap. Ele primeiro constrói um heap máximo (ou mínimo) a partir dos dados. Em seguida, remove repetidamente o elemento raiz do heap (que é o maior ou menor elemento) e o coloca no final da matriz ordenada, reconstruindo o heap com os elementos restantes. O processo se repete até que o heap esteja vazio.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::swap
// Função para manter a propriedade de heap máximo
void maxHeapify(std::vector<int>& arr, int heapSize, int rootIndex) {
int largest = rootIndex;
int leftChild = 2 * rootIndex + 1;
int rightChild = 2 * rootIndex + 2;
if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest != rootIndex) {
std::swap(arr[rootIndex], arr[largest]);
maxHeapify(arr, heapSize, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// Constrói um heap máximo
for (int i = n / 2 - 1; i >= 0; --i) {
maxHeapify(arr, n, i);
}
// Extrai elementos um por um do heap
for (int i = n - 1; i > 0; --i) {
std::swap(arr[0], arr[i]); // Move o maior elemento para o final
maxHeapify(arr, i, 0); // Chama maxHeapify no heap reduzido
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> data(n);
for (int i = 0; i < n; ++i) {
std::cin >> data[i];
}
heapSort(data);
for (int i = 0; i < n; ++i) {
std::cout << data[i] << ' ';
}
std::cout << std::endl;
return 0;
}
A representação de grafo por matriz de adjacências usa uma matriz bidimensional onde a entrada (i, j) indica a presença ou o peso de uma aresta entre o vértice i e o vértice j. É simples para grafos densos, mas pode ser ineficiente em termos de espaço para grafos esparsos.
#include <iostream>
#include <vector>
#include <climits> // Para INT_MAX
#include <unordered_map>
const int MAX_VERTICES = 100;
typedef char VertexData; // Tipo de dado dos vértices
struct AMGraph {
VertexData vexs[MAX_VERTICES]; // Lista de vértices
int arcs[MAX_VERTICES][MAX_VERTICES]; // Matriz de adjacências (pesos)
int vexNum, arcNum; // Número atual de vértices e arestas
};
// Localiza o índice de um vértice com base em seu valor
int locateVertex(const AMGraph& G, VertexData vertexValue, const std::unordered_map<VertexData, int>& vertexMap) {
auto it = vertexMap.find(vertexValue);
if (it != vertexMap.end()) {
return it->second;
}
return -1; // Vértice não encontrado
}
// Cria um grafo não direcionado a partir da entrada
bool createUDN(AMGraph& G) {
std::cout << "Digite o número de vértices e arestas: ";
std::cin >> G.vexNum >> G.arcNum;
std::unordered_map<VertexData, int> vertexMap;
// Inicializa vértices e mapeamento
std::cout << "Digite os vértices: ";
for (int i = 0; i < G.vexNum; ++i) {
std::cin >> G.vexs[i];
vertexMap[G.vexs[i]] = i;
}
// Inicializa a matriz de adjacências com um valor indicando ausência de aresta
const int NO_EDGE = INT_MAX;
for (int i = 0; i < G.vexNum; ++i) {
for (int j = 0; j < G.vexNum; ++j) {
G.arcs[i][j] = NO_EDGE;
}
}
// Lê e preenche a matriz de adjacências
std::cout << "Digite as arestas (vértice1 vértice2 peso): ";
for (int k = 0; k < G.arcNum; ++k) {
VertexData v1_val, v2_val;
int weight;
std::cin >> v1_val >> v2_val >> weight;
int v1_idx = locateVertex(G, v1_val, vertexMap);
int v2_idx = locateVertex(G, v2_val, vertexMap);
if (v1_idx != -1 && v2_idx != -1) {
G.arcs[v1_idx][v2_idx] = weight;
G.arcs[v2_idx][v1_idx] = weight; // Grafo não direcionado
} else {
std::cerr << "Erro: Vértice inválido fornecido para a aresta." << std::endl;
return false;
}
}
return true;
}
// Imprime informações do grafo
void printGraph(const AMGraph& G) {
const int NO_EDGE = INT_MAX;
std::cout << "Número de vértices: " << G.vexNum << ", Número de arestas: " << G.arcNum << std::endl;
std::cout << "Vértices: ";
for (int i = 0; i < G.vexNum; ++i) {
std::cout << G.vexs[i] << " ";
}
std::cout << std::endl;
std::cout << "Matriz de Adjacências:" << std::endl;
for (int i = 0; i < G.vexNum; ++i) {
for (int j = 0; j < G.vexNum; ++j) {
if (G.arcs[i][j] == NO_EDGE) {
std::cout << "INF ";
} else {
std::cout << G.arcs[i][j] << " ";
}
}
std::cout << std::endl;
}
}
int main() {
AMGraph graph;
if (createUDN(graph)) {
printGraph(graph);
} else {
std::cout << "Falha ao criar o grafo." << std::endl;
}
return 0;
}
A representação por lista de adjacências usa uma matriz de ponteiros onde cada índice corresponde a um vértice. Cada entrada aponta para uma lista encadeada de vértices adjacentes. Esta estrutura é mais eficiente em termos de espaço para grafos esparsos.
#include <iostream>
#include <vector>
#include <unordered_map>
const int MAX_VERTICES_AL = 100;
typedef char VertexDataAL;
// Estrutura para um nó na lista de adjacências (representa uma aresta)
struct ArcNode {
int adjVexIndex; // Índice do vértice adjacente
ArcNode *nextArc; // Ponteiro para o próximo nó de aresta
};
// Estrutura para um nó de vértice na lista de adjacências
struct VNode {
VertexDataAL data; // Dado do vértice
ArcNode *firstArc; // Ponteiro para o primeiro nó de aresta (lista de adjacências)
};
// Estrutura principal para o grafo em lista de adjacências
struct ALGraph {
VNode vertices[MAX_VERTICES_AL]; // Array de nós de vértice
int vexNum, arcNum; // Número de vértices e arestas
};
// Localiza o índice de um vértice com base em seu valor
int locateVertexAL(const ALGraph& G, VertexDataAL vertexValue, const std::unordered_map<VertexDataAL, int>& vertexMap) {
auto it = vertexMap.find(vertexValue);
if (it != vertexMap.end()) {
return it->second;
}
return -1; // Vértice não encontrado
}
// Cria um grafo direcionado a partir da entrada
bool createDN_AL(ALGraph& G) {
std::cout << "Digite o número de vértices e arestas: ";
std::cin >> G.vexNum >> G.arcNum;
std::unordered_map<VertexDataAL, int> vertexMap;
// Inicializa vértices e mapeamento
std::cout << "Digite os vértices: ";
for (int i = 0; i < G.vexNum; ++i) {
std::cin >> G.vertices[i].data;
G.vertices[i].firstArc = nullptr; // Inicializa a lista de adjacências como vazia
vertexMap[G.vertices[i].data] = i;
}
// Lê e preenche as listas de adjacências
std::cout << "Digite as arestas (vértice_origem vértice_destino): ";
for (int k = 0; k < G.arcNum; ++k) {
VertexDataAL v1_val, v2_val;
std::cin >> v1_val >> v2_val;
int v1_idx = locateVertexAL(G, v1_val, vertexMap);
int v2_idx = locateVertexAL(G, v2_val, vertexMap);
if (v1_idx != -1 && v2_idx != -1) {
// Cria novo nó de aresta para v1 -> v2
ArcNode *newArc1 = new ArcNode;
newArc1->adjVexIndex = v2_idx;
newArc1->nextArc = G.vertices[v1_idx].firstArc; // Insere no início da lista de v1
G.vertices[v1_idx].firstArc = newArc1;
// Para grafos não direcionados, adicione a aresta de volta
// Se for direcionado, remova o código abaixo
ArcNode *newArc2 = new ArcNode;
newArc2->adjVexIndex = v1_idx;
newArc2->nextArc = G.vertices[v2_idx].firstArc; // Insere no início da lista de v2
G.vertices[v2_idx].firstArc = newArc2;
} else {
std::cerr << "Erro: Vértice inválido fornecido para a aresta." << std::endl;
// É importante liberar a memória alocada aqui em um cenário real
return false;
}
}
return true;
}
// Imprime a lista de adjacências do grafo
void printALGraph(const ALGraph& G) {
std::cout << "Representação em Lista de Adjacências:" << std::endl;
for (int i = 0; i < G.vexNum; ++i) {
std::cout << "Vértice " << G.vertices[i].data << ": ";
ArcNode *current = G.vertices[i].firstArc;
while (current != nullptr) {
std::cout << G.vertices[current->adjVexIndex].data << " -> ";
current = current->nextArc;
}
std::cout << "NULL" << std::endl;
}
}
int main() {
ALGraph graph;
if (createDN_AL(graph)) {
printALGraph(graph);
} else {
std::cout << "Falha ao criar o grafo." << std::endl;
}
// Lembrete: É crucial liberar a memória alocada para ArcNode em um programa completo.
// Isso geramlente seria feito em uma função de destruição.
return 0;
}