Algoritmos

Algoritmos de ordenación
Sebastián Gurin (Cancerbero)
Copyright © 2004 by Sebastián Gurin
Revision History
Revision 1 30 de noviembre de 2004 Revised by: Cancerbero

Sobre la licencia de este documento
Copyright (c) 2004 Sebastián Gurin (Cancerbero). Permission is granted to
copy, distribute and/or modify this document under the terms of the GNU
Free Documentation License, Version 1.1 orany later version published by
the Free Software Foundation; with no Invariant Sections, with no
Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is
included in the section entitled "GNU Free Documentation License

Sobre la licencia del código fuente que aparece en este
documento.
El código de los algoritmos que aparecen en este documento se deja libre al
dominiopúblico. Esto se deja explícito en el siguiente apartado:
Algoritmos de ordenación Copyright (C) 2004 Sebastián Gurin (Cancerbero)
This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option) any
later version.
This program is distributedin the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place, Suite 330, Boston, MA02111-1307 USA

1

Algoritmos de ordenación
Discusión sobre varios
algoritmos de ordenación y sus
características.

1. Introducción
En este documento se estudiará el problema de ordenar un array de elementos sobre los
cuales se puede establecer una relación de orden (i.e los operadores , = tienen
sentido).
Los algoritmos de este documento serán escritos en C y serán intercambiables entresi;
es decir, todos aceptarán los mismos parámetros: un array A de datos y un entero que
representa el tamaño del array.
Si bien en todo este documento se mostrará como ordenar de forma creciente (de
menor a mayor), esperamos que el lector no tenga problemas realizar las
modificaciones pertinentes (que deberán ser obvias) en los algoritmos para poder
ordenar de forma decreciente.
El array deentrada A tendrá elementos de tipo Dato los cuales podrán ser cualquier
tipo de dato representable (una estructura, un objeto de una clase en particular, un
número, un string, etc). Dicho array será usado al estilo C, es decir los índices de los N
elementos de A serán 0, 1, 2, ..., N-1.
Se supondrá por simplicidad que los datos aceptan el uso de operadores "". Si
bien esto no será así en lapráctica, no perderemos generalidad. La estrategia para
establecer un orden entre los elementos dependerá de la tecnología que usemos para
implementar el algoritmo de ordenación. En Appendix A se discute esto con más
profundidad y para tres tecnologías de programación distintas: programación
estruturada (C), programación orientada a objetos (C++) y programación de objetos
(Smalltalk, Self,etc.)
También se utilizará el operador de asignación de manera especial en algunos casos.
Por ejemplo, en el siguiente segmento de código, en tmp se almacenará una copia del
iésimo elemento del array A de entrada.
Dato tmp;
/* ... */
tmp = A[i];

2

Algoritmos de ordenación
Junto con la descripción de cada algoritmo también se discutirá el orden de tiempo de
ejecución del mismo. Seutilizará para esto la notación de ordenes de magnitud "O
grande" ("big oh"), descripta en el documento "Análisis de Algoritmos" del mismo
autor (ver Referencias). La medición de estos tiempos ha sido hecha considerando
solamente la cantidad de comparaciones, asignaciónes, etc que impliquen elementos del
array de datos: o sea, las cotas de tiempo sólo están en función del tamaño del conjunto...