Sorting algorithm - Quick Sort
-
Este algoritmo es muy comun, por que es facil de implementar y ademas este puede ser utilizado con grandes cantidades de datos. Les dejo la implementación en C++.
vector<int> quickSort(vector<int> data) { int n = data.size(), i; if (n <= 1) return data; int middle = data[n/2]; vector<int> left; vector<int> right; for (i = 0; i < n; i++) { if (i != n/2) { if (data[i] <= middle) left.PB(data[i]); else right.PB(data[i]); } } i = 0; left = quickSort(left); for (int j=0; j < left.size() ;j++) data[i++] = left[j]; data[i++] = middle; right = quickSort(right); for (int j=0; j < right.size() ;j++) data[i++] = right[j]; return data; }
A continuación un ejemplo de como es la ejecución de este algoritmo.
{18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11} // input, Array desordenado {6, 9, 1, 4, 12, 5, 6, 7, 11} {15} {18} // middle = {15} {6, 9, 1, 4, 5, 6, 7, 11} {12} {15} {18} // middle = {12} {1, 4} {5} {6, 9, 6, 7, 11} {12} {15} {18} // middle = {5} {1} {4} {5} {6} {6} {9, 7, 11} {12} {15} {18} // middle = {1} y {6} {1} {4} {5} {6} {6} {7} {9, 11} {12} {15} {18} // middle = {7} {1} {4} {5} {6} {6} {7} {9} {11} {12} {15} {18} // middle = {9}