Comparto con ustedes un programa en C ANSI 89 que muestra la implementación de cuatro algoritmos de ordenamient: Burbuja, Selección, Inerción y una implementación básica de Quicksort son optimizaciones. Espero este ejemplo siva a todos los estudiantes para ver la aplicación de estos algoritmos.
La licencia es GPL 3 así que ya saben, pueden copiar y pegar sin problema siempre y cuando el nuevo código esté disponible bajo GPL 3 o superior.
/*
* Escrito por Jesús Manuel Mager Hois
* el 27 de abril de 2009, tomando referencias
* de Wikipedia.
*
* Descripción: Programa que genera listas
* aleatorias para después
* ordenarlas con los algoritmos
* de burbuja, selección,
* inserción y quicksort.
*
* Todos los algoritmos son simples,
* y representan únicamente
* las ideas básicas detrás de
* cada algoritmo.
*
* Lenguaje: ANSI C
*
* Bajo licencia GPL 3
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define V_SIZE 10
int cont;
// Herramientas
void gen_rand(int v[], int size);
void print_vect(int v[], int size);
void swap(int v[], int o, int d);
//Algoritmos
void bubble_sort(int v[], int size);
void insert_sort(int v[], int size);
void select_sort(int v[], int size);
void quick_sort(int v[], int size);
void q_sort(int v[], int left, int right);
//void quick_sort(int v[], int size);
int main(int argc, char *argv[])
{
int v[V_SIZE];
printf("---------------------------------------------------\n");
printf("UNAM FCA SUA\n");
printf("Materia: Informática III\n");
printf("Alumno: Jesús Manuel Mager Hois\n");
printf("---------------------------------------------------\n");
printf("Este programa genera listas aleatorias que son\n");
printf("ordenadas por los siguientes algoritmos: bubblesort\n");
printf("insert sort, selecction sort y quicksort. Todos\n");
printf("son ejemplos sencillos que solo pretenden mostrar\n");
printf("los conecpts básicos de cada uno.\n");
printf("Por J. M. 2009 Bajo GPL 3. (ver código fuente)\n");
printf("############ Ordenando con Burbuja ############\n");
gen_rand(v, V_SIZE);
printf("No. Aleatorios: ");
print_vect(v, V_SIZE);
bubble_sort(v, V_SIZE);
printf("No. Ordenados : ");
print_vect(v, V_SIZE);
printf("############ Ordenando por Inserción ##########\n");
gen_rand(v, V_SIZE);
printf("No. Aleatorios: ");
print_vect(v, V_SIZE);
insert_sort(v, V_SIZE);
printf("No. Ordenados : ");
print_vect(v, V_SIZE);
printf("############ Ordenando por Selección ##########\n");
gen_rand(v, V_SIZE);
printf("No. Aleatorios: ");
print_vect(v, V_SIZE);
select_sort(v, V_SIZE);
printf("No. Ordenados : ");
print_vect(v, V_SIZE);
printf("############ Ordenando por Quicksort ##########\n");
gen_rand(v, V_SIZE);
printf("No. Aleatorios: ");
print_vect(v, V_SIZE);
quick_sort(v, V_SIZE);
printf("No. Ordenados : ");
print_vect(v, V_SIZE);
return 0;
}
void gen_rand(int v[], int size)
{
int i;
cont = cont + 1;
srand(time(NULL)*cont);
for(i=0; i<size; i++)
v[i]=rand()%100;
}
void print_vect(int v[], int size)
{
int i;
printf("[ ");
for(i=0; i<size; i++)
printf("%d ", v[i]);
printf("]\n");
}
void swap(int v[], int o, int d)
{
int temp;
temp=v[d];
v[d]=v[o];
v[o]=temp;
}
void bubble_sort(int v[], int size)
{
int i, j;
for (j=0; j<size; j++)
for (i=0; i<size-1; i++)
if(v[i]>v[i+1])
swap(v, i, i+1);
}
void insert_sort(int v[], int size)
{
int i, j, temp;
for(i=0; i<size; i++)
{
temp=v[i];
j=i-1;
while(j>=0 && v[j] >temp)
{
v[j+1] = v[j];
j--;
}
v[j+1] = temp;
}
}
void select_sort(int v[], int size)
{
int i, j, min;
for (i=0; i<size; i++)
{
min=i;
for(j=i+1; j< size; j++)
if(v[min]>v[j])
min=j;
swap(v, min, i);
}
}
void quick_sort(int v[], int size)
{
q_sort(v, 0, size-1);
}
void q_sort(int v[], int left, int right)
{
int pivot, lTmp, rTmp;
lTmp=left;
rTmp=right;
pivot=v[left];
while ( left < right )
{
while((v[right] >= pivot) && (left < right))
right--;
if(left != right)
{
v[left]=v[right];
left++;
}
while ((v[left] <= pivot) && (left<right))
left++;
if(left!=right)
{
v[right]=v[left];
right--;
}
}
v[left]=pivot;
pivot=left;
left=lTmp;
right=rTmp;
if(left<pivot)
q_sort(v, left, pivot-1);
if(right>pivot)
q_sort(v, pivot+1, right);
}
