UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

Facultad de Ingeniería

Método de ordenación rápida "quicksort"

Alumno:
Lugo Martínez Germán
Profesor: Ing. Lugo Martínez Germán
Grupo: 37
Semestre: 2025-1 14 de noviembre de 2024
Universidad Nacional
Autónoma de México Fundamentos de programación

Índice
1. Introducción 2

2. Descripción del algoritmo 2

3. Análisis 2

4. Diseño 4
4.1. Pesudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2. Diagrama de flujo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

5. Implementación 6

6. Pruebas 7

7. Conclusiones 8

1
Universidad Nacional
Autónoma de México Fundamentos de programación

Método de ordenación rápida "quicksort"

1. Introducción
En C, los métodos de ordenamiento son algoritmos que se utilizan para reorganizar los elementos de
una lista o arreglo en un orden específico, generalmente ascendente o descendente. Estos algoritmos son
fundamentales en programación, y cada uno tiene sus ventajas y desventajas en términos de eficiencia y
complejidad.

2. Descripción del algoritmo

El método de ordenación rápida (quicksort) para ordenar o clasificar un vector o lista de elementos
(array) se basa en el hecho de que es más rápido y fácil de ordenar dos listas pequeñas que una lista grande.
Se denomina método de ordenación rápida porque, en general, puede ordenar una lista de datos mucho más
rápidamente que cualquier otro método.
Este método se basa en la estrategia típica de "divide y vencerás"(divide and conquer). La lista a clasificar
almacenada en un vector o array se divide en dos sublistas: una con todos los valores menores o iguales
a un cierto valor específico y otra con todos los valores mayores que ese valor. El valor elegido puede ser
cualquier valor arbitrario del vector. En ordenación rápida se llama a ese valor: pivote.
El primer paso es dividir la lista original en dos sublistas o subvectores y un valor de separación.
Así, el vector V se divide en tres partes:

Subvector VI, que contiene los valores inferiores o iguales.

El elemento de separación.

Subvector VD, que contiene los valores superiores o iguales.

Los vectores VI y VD no están ordenados, excepto en el caso de reducirse a un elemento.

3. Análisis
Para una entrada:
[ 18 11 27 13 9 4 16 ]

2
Universidad Nacional
Autónoma de México Fundamentos de programación

Se elije el pivote: 13. Se recorre la lista desde el extremo izquierdo y se busca un elemento mayor que
13 (se encuentra el 18). A continuación, se busca desde el extremo derecho un valor menor que 13 (se
encuentra el 4).

[ 18 11 27 13 9 4 16 ]

Se intercambian estos dos valores y se produce la lista:

[4 11 27 13 9 18 16 ]

Se isigue recorriendo el vector por la izquierda y se localiza el 27, y a continuación otro valor bajo se
encuentra a la derecha (el 9). Intercambiar estos dos calores y se obtiene:

[4 11 9 13 27 18 16 ]

Al intentar este proceso una vez más, se encuentra que las exploraciones de los dos extremos vienen juntos
sin encontrar ningún futuro valor que esté "fuera de lugar". En este punto se conoce que todos los valores a
la derecha son mayores que todos los valores a la izquierda del pivote. Se ha realizado una partición en la
lista original, que ha quedado dividida en dos listas más pequeñas:

[4 11 9 [13] 27 18 16 ]

Ninguna de amabas listas está ordenada; sin embargo, basados en los resultados de esta primera parti-
ción, se pueden ordenar ahora las dos particiones independiente. Esto es, si ordenamos la lista:

[4 11 9]

y su posición, y la lista:

[ 27 18 16 ]

de igual forma, la lista completa estará ordenada:

[4 9 11 13 16 18 27 ]

El procedimeinto de ordenación supone, en primer lugar, una partición de la lista.

3
 Universidad Nacional
Autónoma de México Fundamentos de programación

4. Diseño
4.1. Pesudocódigo
A continuación se muestra el pseudocódigo para el algoritmo:
1 INICIO
2 Llenar ( A )
3 Algoritmo quicksort (A , inf , sup )
4 i <- inf
5 j <- sup
6 x <- A [( inf + sup ) div 2]
7 mientras i <= j hacer
8 mientras A [ i ] < x hacer
9 i <- i + 1
10 fin_mientras
11 mientras A [ j ] > x hacer
12 j <- j - 1
13 fin_mientras
14 si i <= j entonces
15 tam <- A [ i ]
16 A [ i ] <- A [ j ]
17 A [ j ] <- tam
18 i <- i + 1
19 j <- j - 1
20 fin_si
21 fin_mientras
22 si inf < j
23 llamar_a quicksort (A , inf , j )
24 fin_si
25 si i < sup
26 llamar_a quicksort (A , i , sup )
27 fin_si
28 FIN

4
Universidad Nacional
Autónoma de México Fundamentos de programación

4.2. Diagrama de flujo

A continuación se muestra el diagrama de flujo para el algoritmo:

Figura 1: Diagrama de flujo

5
 Universidad Nacional
Autónoma de México Fundamentos de programación

5. Implementación
El código en lenguaje C que realiza el Método de ordenación rápida "quicksort":
1 # include < stdio .h >
2

3 void swap ( int *a , int * b ) {

4 int t = * a ;
5 *a = *b;
6 *b = t;
7 }
8

9 int partition ( int array [] , int low , int high ) {

10 // Elegir el ultimo elemento como pivote ( puedes elegir otro )
11 int pivot = array [ high ];
12 int i = ( low - 1);
13

14 for ( int j = low ; j <= high - 1; j ++) {

15 // Si el elemento actual es menor o igual al pivote
16 if ( array [ j ] <= pivot ) {
17 i ++;
18 swap (& array [ i ] , & array [ j ]);
19 }
20 }
21 swap (& array [ i + 1] , & array [ high ]);
22 return ( i + 1);
23 }
24

25 void quickSort ( int array [] , int low , int high ) {

26 if ( low < high ) {
27 // pi es el indice de particion
28 int pi = partition ( array , low , high );
29

30 // Ordenar recursivamente los subarreglos antes y despues de la parti

31 quickSort ( array , low , pi - 1);
32 quickSort ( array , pi + 1 , high );
33 }
34 }
35

36 // Funcion para imprimir el arreglo

37 void printArray ( int array [] , int size ) {
38 for ( int i = 0; i < size ; ++ i ) {

6
 Universidad Nacional
Autónoma de México Fundamentos de programación

39 printf ( " %d " , array [ i ]);

40 }
41 printf ( " \ n " );
42 }
43

44 int main () {
45 int data [] = {8 , 7 , 2 , 1 , 0 , 9 , 6};
46 int n = sizeof ( data ) / sizeof ( data [0]);
47

48 printf ( " Arreglo original : \ n " );

49 printArray ( data , n );
50

51 quickSort ( data , 0 , n - 1);

52

53 printf ( " Arreglo ordenado : \ n " );

54 printArray ( data , n );
55

56 return 0;
57 }

6. Pruebas
Para la siguiente entrada:
[8 7 2 1 0 9 6]

La salida del programa es:

Figura 2: Salida del programa

7
Universidad Nacional
Autónoma de México Fundamentos de programación

7. Conclusiones
El Quicksort es uno de los algoritmos de ordenación más eficientes y ampliamente utilizados debido
a su rendimiento promedio y su implementación relativamente sencilla. A continuación, se presentan las
principales conclusiones sobre este método:

Ventajas:

Eficiencia promedio: En el caso promedio, Quicksort tiene una complejidad temporal de O(n log n),
lo que lo convierte en un algoritmo muy rápido para grandes conjuntos de datos.

In-place: No requiere memoria adicional para realizar el ordenamiento, lo que lo hace eficiente en
términos de uso de espacio.

Versátil: Se puede adaptar a diferentes tipos de datos y estructuras de datos.

Recursividad: Su implementación recursiva es elegante y fácil de entender, aunque puede llevar a

problemas de pila si no se maneja correctamente.

Desventajas:

Peor caso: En el peor caso, Quicksort tiene una complejidad temporal de O(n²), lo que ocurre cuando
la partición siempre genera subarreglos desbalanceados (por ejemplo, cuando el pivote es siempre el
elemento más grande o más pequeño).

No estable: No garantiza mantener el orden relativo de elementos iguales.

Recursividad: La recursividad puede consumir recursos adicionales en sistemas con poca memoria.

Consideraciones adicionales:

Elección del pivote: La elección del pivote es crucial para el rendimiento de Quicksort. Una buena
elección del pivote puede reducir significativamente el número de comparaciones y mejorar el tiempo
de ejecución.

Optimizaciones: Existen diversas técnicas para optimizar Quicksort, como la optimización de la cola
corta, el uso de introspective sort y la elección de pivotes aleatorios.

Aplicaciones: Quicksort se utiliza en una amplia variedad de aplicaciones, desde sistemas operativos
hasta bases de datos y bibliotecas de programación.

En resumen, Quicksort es un algoritmo de ordenación muy potente y versátil, pero su rendimiento

depende en gran medida de la implementación y la elección del pivote. En la mayoría de los casos, es una
excelente opción para ordenar grandes conjuntos de datos.