🚀 go-pugleaf

--nextPart1261528.STq1LpRCxx
Content-Type: text/plain; charset=iso-8859-15
Content-Transfer-Encoding: 8Bit

Bubble,Insert,Select,Merge y QuickSort:

Juntos en un mismo fuente, facilmente convertible a librer�a, con interfaz
com�n entre s� [0], con un interfaz de parametros [1] para probar todos
desde el mismo ejecutable.

[0] int nombreSort(int *T,int P, int U);
T:array de enteros
P:indice del Primer elemento
U:indice del �ltimo elemento

[1] ./sort.x [letra] [numero]
letra:b|i|s|m|q la inicial del algoritmo
numero:tama�o de la tabla que se permuta

OJO! No est�n opptimizados para eficiencia en C, ni llevan apenas Control de
Errores, es c�digo limpio para facilitar el an�lisis de Algoritmos, lo m�s
cercano posible al pseudoc�digo de la UAM (Aut�noma de Madrid), a mi me han
llevado un par de horas y esto es para ahorraroslas a vosotros.

Podeis compilar con [2], y os ahorrais el makefile

[2]gcc -Wall -ansi -pedantic-errors -ggdb -lm sort.c -o sort.x

-- 
fer# linux user 298351
--nextPart1261528.STq1LpRCxx
Content-Type: text/x-csrc; name="sort.c"
Content-Transfer-Encoding: 8Bit
Content-Disposition: attachment; filename="sort.c"

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>/*INT_MAX*/
#include <math.h>/*floor*/
#include <string.h>/*memmove*/

#define OK 0
#define ERR -1

/* utileria matem�tica comun */
int aleat(int,int);
int *genera_perm(int);

/*utileria de representacion*/
void imprimeTabla(int *,int );

/* algoritmos Locales */
int bubbleSort(int*,int,int);
int insertSort(int*,int,int);
int selectSort(int*,int,int);
	/*minimo de selectsort*/
	int min(int*,int,int);

/* algoritmos Divide y Venceras */
int mergeSort(int*,int,int);
	/*combinar de mergeSort*/
	int merge(int*,int,int,int);

int quickSort(int*,int,int);
	/*partir de qsort*/
	int partir(int*,int,int);
		int medio(int*,int,int);


int main(int argc, char **argv){
	int *T,n; /* tabla y numero de elementos */

	if (argc!=3) {
		printf("%s [algoritmo: i|s|b|m|q] [numero de elementos]\n",argv[0]);
		return 1;
	}
	if ( ( n = atoi(argv[2]) ) == 0 ) return 1;

	T = genera_perm(n);
	/*imprimir antes de ordenar */
	printf("\nTabla desordenada:");
	imprimeTabla(T,n);

	switch (argv[1][0]) {
		case 'b':
			printf("\nBubbleSort:\n");
			bubbleSort(T,0,n-1);
			break;
		case 'i':
			printf("\nInsertSort:\n");
			insertSort(T,0,n-1);
			break;
		case 's':
			printf("\nSelectSort:\n");
			selectSort(T,0,n-1);
			break;
		case 'm':
			printf("\nMergeSort:\n");
			mergeSort(T,0,n-1);
			break;
		case 'q':
			printf("\nQuickSort:\n");
			quickSort(T,0,n-1);
			break;
		default:
			printf("\nAlgoritmo desconocido\n");
			return 1;
	}/*fin de switch*/

	/*imprimir despues de ordenar */
	printf("\nTabla ordenada:");
	imprimeTabla(T,n);

	return 0;
}

int aleat(int P, int U){
int n;
	if (P>U) return INT_MAX;
	n = U-P+1;
return (int) ( P + n * (1.0 * rand() / RAND_MAX) );
}

int * genera_perm(int n) {
    int *perm;
    int aux, i, j;
    if ( (perm=(int *)malloc(n * sizeof(int))) == NULL){
        printf("\ngeneraperm: No hay memoria");
        return NULL;
    } /*fin de if*/

    for(i=0; i<n; i++)
        perm[i]=i+1;

    for(i=0; i<n; i++){
        aux=perm[i];
        if ((j=aleat(i,n-1))==INT_MAX){
            free(perm);
            printf("\ngeneraperm: Fallo de aleat");
            return NULL;
        }
        perm[i]=perm[j];
        perm[j]=aux;
    } /*fin de for*/
    return perm;/*solo llegamos aqui si todo ha ido bien*/
}/* Fin de genera_perm*/

void imprimeTabla(int *T,int n){
	int i;

	printf("\n");
	for (i=0;i<n;i++){
		printf("%d ",T[i]);
	}
	printf("\n");

	}

int bubbleSort(int *T, int P, int U){
int i,aux;
int n=U-P+1;
	/*conrol de parametros*/
	if (P>U) return ERR;

	while (P<U){
		for(i=P;i<U;i++){
			if (T[i]>T[i+1]) {
				aux=T[i+1];
				T[i+1]=T[i];
				T[i]=aux;
				imprimeTabla(T,n);
			}
		}
	U--;
	}
	return OK;
}

int insertSort(int *T,int P,int U) {
int i,j,A;
	/*control de parametros*/
	if (P>U) return ERR;

	for(i=P+1;i<=U;i++){
		A=T[i];
		j=i;

		while ((j>P) && (T[j-1]>A)) {
			T[j]=T[j-1];
			j--;
			/*traza*/
			imprimeTabla(T,U-P+1);
		}
		T[j]=A;
	}
	return OK;
}

int selectSort(int *T,int P,int U){
int i, m, aux;
	/*control de parametros*/
	if (P>U) return ERR;
	i=P;
	while (i<U){
		m = min(T,i,U);
		/*printf("\tPaso %d, min=%d\n",i,T[m]);*/

		/* swap */
		aux=T[i]; T[i]=T[m]; T[m]=aux;

		i++;

		imprimeTabla(T,U-P+1);
	}
	return OK;
}

/*devuelve el m�nimo de un subtabla*/
/*eficiencia O(N)*/
int min(int *T,int P, int U){
int min,i;
	if (P>U) return ERR;
	min = P;
	for (i=P; i<=U; i++){
		if (T[i] < T[min]){
			min = i;
		}
	}
	return min;
}

int mergeSort(int *T,int P,int U){
int M;
	/*control de par�metros*/
	if (P>U) return ERR;
	if (P==U) return OK; /*caso base*/

	imprimeTabla(T,U-P+1);

	M=(int)(P + floor((U-P)/2));

	if (mergeSort(T, P, M)==ERR){
		return ERR;
	}
	if (mergeSort(T, M+1, U)==ERR) {
		return ERR;
	}
	/*combinamos las tablas*/
	return merge(T,P,U,M);
}/*fin de mergeSort*/

int merge(int *T, int P, int U, int M){
int *Taux, i, j, k;
int n=(U-P+1); /*numero de elementos*/
	/*control de parametros*/
	if (P>U) return ERR;

	/*reserva de memoria*/
	if ((Taux=(int *)malloc( n * sizeof(int)))==NULL) return ERR;

	i=P; j=M+1; k=0;

	while ((i<=M)&&(j<=U)&&(k<n)){
		if (T[i]<T[j]){
			Taux[k]=T[i];
			i++;
		} else {
			Taux[k]=T[j];
			j++;
		}
		k++;
	}/*fin de for*/

	if (i<=M){
		while(i<=M){
			Taux[k]=T[i];
			k++;
			i++;
		}
	}else{
		while (j<=U){
			Taux[k]=T[j];
			k++;
			j++;
		}
	}
	memmove(T+P,Taux,n*sizeof(int));/*copiamos Taux sobre T*/

	free(Taux);/*liberamos la memoria auxiliar*/

return OK;
}/*fin de merge*/

int quickSort(int *T, int P, int U){
int M;
	/*conrol de parametros*/
	if (P>U) return ERR;
	if (P==U) return OK; /*caso base*/

	M=partir(T,P,U);
	if (quickSort(T,P,M)==ERR)
		return ERR;
	if (quickSort(T,M+1,U)==ERR)
		return ERR;
return OK;
}

int partir(int *T, int P, int U){
int i, M, pivote, aux;

	if ((M=medio(T,P,U))==ERR) return ERR;
	pivote=T[M];

	/*swap(T[P],T[M])*/
	aux=T[M]; T[M]=T[P]; T[P]=aux;
	M=P;
	for(i=P+1;i<=U;i++){
		if(T[i]<pivote){
			M++;
			/*swap(T[i],T[M])*/
			aux=T[i]; T[i]=T[M]; T[M]=aux;
		}
	}
	/*swap(T[P],T[M])*/
	aux=T[M]; T[M]=T[P]; T[P]=aux;
return M;
}/*fin de partir*/

int medio(int *T,int P,int U){
/*
  Buscar el verdadero elemento medio empeora en
  todos los caso excepto en tablas ya ordenadas
*/
return (P<U?P:ERR);/*detecta errores en P,U*/
}


--nextPart1261528.STq1LpRCxx--