C Algoritmos de ordenamiento
Ordenamiento de burbuja
El ordenamiento de burbuja (en inglés: Bubble Sort) es un algoritmo de ordenamiento simple. Recorre repetidamente la secuencia a ordenar, comparando dos elementos a la vez, e intercambiándolos si su orden (por ejemplo, de mayor a menor, o de la primera letra de A a Z) es incorrecto.
Demostración del proceso:
Ejemplo
#include <stdio.h>
// Declaración de la función
void bubble_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
bubble_sort(arr, len); // Llamar a la función de ordenamiento de burbuja
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Función de ordenamiento de burbuja
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
// Intercambiar posiciones de elementos
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Ordenamiento por selección
El ordenamiento por selección (Selection sort) es un algoritmo de ordenamiento simple e intuitivo. Su principio de funcionamiento es el siguiente: primero se encuentra el elemento más pequeño (o más grande) en la secuencia no ordenada y se coloca en la posición inicial de la secuencia ordenada; luego, se continúa buscando el elemento más pequeño (o más grande) entre los elementos restantes no ordenados y se coloca al final de la secuencia ya ordenada. Así sucesivamente, hasta que todos los elementos estén ordenados.
Demostración del proceso:
Ejemplo
#include <stdio.h>
// Declaración de la función
void selection_sort(int a[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
selection_sort(arr, len); // Llamar a la función de ordenamiento por selección
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Función de ordenamiento por selección
void selection_sort(int a[], int len) {
for (int i = 0; i < len - 1; i++) {
int min = i; // Registrar la posición del valor mínimo; por defecto, el primer elemento es el mínimo
for (int j = i + 1; j < len; j++) {
if (a[j] < a[min]) { // Encontrar el valor mínimo actual
min = j; // Registrar la posición del valor mínimo
}
}
// Intercambiar dos variables
if (min != i) {
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
/*// Función de intercambio personalizada
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}*/
Ordenamiento por inserción
El ordenamiento por inserción (en inglés: Insertion Sort) es un algoritmo de ordenamiento simple e intuitivo. Su principio de funcionamiento consiste en construir una secuencia ordenada; para los datos no ordenados, se escanea de atrás hacia adelante en la secuencia ya ordenada, se encuentra la posición correspondiente y se inserta. En la implementación, el ordenamiento por inserción suele adoptar el ordenamiento in-place (es decir, un ordenamiento que solo necesita un espacio adicional de {\displaystyle O(1)} {\displaystyle O(1)}), por lo que durante el escaneo de atrás hacia adelante es necesario desplazar repetidamente los elementos ya ordenados hacia atrás
para hacer espacio e insertar el nuevo elemento.Demostración del proceso:
Ejemplo
#include <stdio.h>
// Declaración de la función
void insertion_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
insertion_sort(arr, len); // Llamar a la función de ordenamiento por inserción
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Función de ordenamiento por inserción
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i]; // Elemento actual a insertar
int j = i;
// Mover a la derecha los elementos mayores que temp
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp; // Insertar el elemento en la posición correcta
}
}
Ordenamiento de Shell
El ordenamiento de Shell, también conocido como algoritmo de ordenamiento por incrementos decrecientes, es una versión mejorada y más eficiente del ordenamiento por inserción. El ordenamiento de Shell es un algoritmo de ordenamiento no estable.
El ordenamiento de Shell propone mejoras basándose en las siguientes dos propiedades del ordenamiento por inserción:
- El ordenamiento por inserción es eficiente al operar sobre datos casi ordenados, pudiendo alcanzar una eficiencia de ordenamiento lineal.
- Pero el ordenamiento por inserción generalmente es ineficiente, porque solo puede mover los datos una posición a la vez.
Demostración del proceso:
Ejemplo
#include <stdio.h>
// Declaración de la función
void shell_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
shell_sort(arr, len); // Llamar a la función de ordenamiento de Shell
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Función de ordenamiento de Shell
void shell_sort(int arr[], int len) {
// Calcular el intervalo inicial
for (int gap = len / 2; gap > 0; gap /= 2) {
// Realizar ordenamiento por inserción para cada intervalo
for (int i = gap; i < len; i++) {
int temp = arr[i]; // Elemento actual a insertar
int j = i;
// Mover los elementos mayores que temp
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp; // Insertar el elemento en la posición correcta
}
}
}
Ordenamiento por mezcla
Divide los datos en dos segmentos y, de cada uno, selecciona uno a uno el elemento más pequeño para moverlo al final de un nuevo segmento de datos.
Se puede realizar de arriba hacia abajo o de abajo hacia arriba.
Demostración del proceso:
Método iterativo
#include <stdio.h>
#include <stdlib.h>
// Declaración de la función
int min(int x, int y);
void merge_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
merge_sort(arr, len); // Llamar a la función de ordenamiento por mezcla
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Devuelve el valor mínimo de dos números
int min(int x, int y) {
return x < y ? x : y;
}
// Función de ordenamiento por mezcla
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
if (b == NULL) { // Verificar si la asignación de memoria fue exitosa
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start;
int mid = min(start + seg, len);
int high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
// Fusionar dos subarrays
while (start1 < end1 && start2 < end2) {
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}
while (start1 < end1) {
b[k++] = a[start1++];
}
while (start2 < end2) {
b[k++] = a[start2++];
}
}
// Intercambiar los punteros de los arrays
int* temp = a;
a = b;
b = temp;
}
// Si a y arr no son iguales, copiar el contenido de a de vuelta a arr
if (a != arr) {
for (int i = 0; i < len; i++) {
b[i] = a[i];
}
b = a;
}
free(b); // Liberar memoria
}
Método recursivo
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Declaración de la función
void merge_sort_recursive(int arr[], int reg[], int start, int end);
void merge_sort(int arr[], const int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
merge_sort(arr, len); // Llamar a la función de ordenamiento por mezcla
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Implementación recursiva del ordenamiento por mezcla
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int mid = start + (end - start) / 2;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
// Usar memcpy para copiar el array y mejorar la eficiencia
memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int));
}
// Función de entrada del ordenamiento por mezcla
void merge_sort(int arr[], const int len) {
int* reg = (int*)malloc(len * sizeof(int));
if (reg == NULL) { // Verificar si la asignación de memoria fue exitosa
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
merge_sort_recursive(arr, reg, 0, len - 1);
free(reg); // Liberar memoria
}
Ordenamiento rápido
Se elige aleatoriamente un elemento en el intervalo como pivote; los elementos menores que el pivote se colocan antes de él, y los mayores después; luego se ordenan por separado la zona de menores y la zona de mayores.
Demostración del proceso:
Método iterativo
#include <stdio.h>
// Estructura de rango
typedef struct _Range {
int start, end;
} Range;
// Crear un nuevo rango
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
// Intercambiar dos enteros
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// Función de ordenamiento rápido
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // Evitar que len sea igual a un valor negativo y provoque un error de segmentación (Segment Fault)
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p > 0) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // Seleccionar el punto medio como pivote
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left; // Verificar si el lado izquierdo del pivote cumple el requisito
while (arr[right] > mid) --right; // Verificar si el lado derecho del pivote cumple el requisito
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--; // Mover los punteros para continuar
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
quick_sort(arr, len); // Llamar a la función de ordenamiento rápido
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Método recursivo
#include <stdio.h>
// Intercambiar dos enteros
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// Implementación recursiva del ordenamiento rápido
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (left < right && arr[left] < mid)
left++;
while (left < right && arr[right] >= mid)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
// Función de entrada del ordenamiento rápido
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // Calcular la longitud del array
quick_sort(arr, len); // Llamar a la función de ordenamiento rápido
// Imprimir el array ordenado
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}