Quick Sort
Quick sort coloca el pivote y ordena recursivamente las particiones.
¿Qué es Quick Sort?
Quick sort coloca el pivote y ordena recursivamente las particiones.
Particiona valores alrededor de un pivote.
Puntos importantes
- Prueba entradas vacías, únicas, duplicadas y ordenadas.
- Separa corrección y optimización.
- Prefiere la biblioteca estándar en producción.
Visualizador de Quick Sort
O(n log n)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Ejemplos de código C y C++
main.c
#include <stdio.h>
void swap(int *left, int *right) {
int temporary = *left;
*left = *right;
*right = temporary;
}
int partition(int *values, int low, int high) {
int pivot = values[high];
int boundary = low;
for (int scan = low; scan < high; ++scan) {
if (values[scan] < pivot) {
swap(&values[boundary++], &values[scan]);
}
}
swap(&values[boundary], &values[high]);
return boundary;
}
void quick_sort(int *values, int low, int high) {
if (low >= high) return;
int pivot = partition(values, low, high);
quick_sort(values, low, pivot - 1);
quick_sort(values, pivot + 1, high);
}
int main(void) {
int values[] = {9, 4, 7, 3, 10, 5};
quick_sort(values, 0, 5);
for (int index = 0; index < 6; ++index) {
printf("%d ", values[index]);
}
}
3 4 5 7 9 10C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
if (last - first < 2) return;
auto pivot = *(last - 1);
auto middle = std::partition(first, last - 1,
[pivot](int value) { return value < pivot; });
std::iter_swap(middle, last - 1);
quick_sort(first, middle);
quick_sort(middle + 1, last);
}
int main() {
std::vector values{9, 4, 7, 3, 10, 5};
quick_sort(values.begin(), values.end());
for (int value : values) {
std::cout << value << ' ';
}
}
3 4 5 7 9 10Comparación entre C y C++
Promedio O(n log n), pivotes malos O(n²). C++ expresa la partición con std::partition.
C
Bucles, punteros, tamaños y buffers se escriben explícitamente.
C++
Iteradores y algoritmos separan la operación del almacenamiento.
Ejercicios prácticos
Ejecuta ambas versiones y modifícalas para observar sus garantías.
- Traza cada comparación.
- Prueba duplicados y valores extremos.
- Compara con la biblioteca estándar.