Leyenda

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.1or any 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 isdistributed in 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
www.detodoprogramacion.com

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 yserán intercambiables entre si;
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 deforma decreciente.
El array de entrada 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 "". Sibien esto no será así en la prá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 deobjetos
(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
www.detodoprogramacion.com

Algoritmos de ordenación
Junto con la descripción de cada algoritmo también sediscutirá el orden de tiempo de
ejecución del mismo. Se utilizará 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...