Aquí está mi clasificación rápida trabajando en una Lista, se supone que debe leer desde un archivo .txt grande que contiene un número por línea. Después de llenar la Lista del archivo, traté de ordenarla, pero por alguna razón está tardando demasiado.
// Main.cs List<int> myList = new List<int>(); string[] lines = System.IO.File.ReadAllLines("largeFile.txt"); foreach (string num in lines) myList.Add(int.Parse(num)); QuickSort(ref myList, 0, myList.Count - 1);rápido.cs:
static void Swap(List<int> myList, int indexA, int indexB) { int tmp = myList[indexA]; myList[indexA] = myList[indexB]; myList[indexB] = tmp; } static int Partition(ref List<int> myList, int leftIdx, int rightIdx) { int pivot = leftIdx - 1; for (int i = leftIdx; i < rightIdx; ++i) { if (myList[i] < myList[rightIdx]) { ++pivot; Swap(myList, pivot, i); } } ++pivot; Swap(myList, pivot, rightIdx); return pivot; } static void QuickSort(ref List<int> myList, int leftIdx, int rightIdx) { if (rightIdx <= leftIdx) return; int pivotIdx = Partition(ref myList, leftIdx, rightIdx); QuickSort(ref myList, leftIdx, pivotIdx - 1); QuickSort(ref myList, pivotIdx + 1, rightIdx); return; }Comparado con List.Sort() (que lo ordena casi de inmediato), esto es ridículamente lento, ¿cómo puedo mejorar esto? Por ejemplo, List.Sort toma 3 milisegundos mientras que mi método toma 14769
Código de ejemplo para el esquema de partición clásico de Lomuto. Intercambia el elemento central con el último elemento que luego se usa como pivote. Recurse en más pequeño, bucle en más grande reduce el espacio de pila a O (log (n)), pero la complejidad del tiempo en el peor de los casos permanece en O (n ^ 2).
static public void QuickSort(int [] a, int lo, int hi) { while (lo < hi){ int t; int p = a[(lo+hi)/2]; // use mid point for pivot a[(lo+hi)/2]= a[hi]; // swap with a[hi] a[hi] = p; int i = lo; for (int j = lo; j < hi; ++j){ // Lomuto partition if (a[j] < p){ // if a[j] < pivot t = a[i]; // swap a[i], a[j] a[i] = a[j]; a[j] = t; ++i; // i += 1 } } t = a[i]; // swap a[i], a[hi] a[i] = a[hi]; // to put pivot in place a[hi] = t; if(i - lo <= hi - i){ // recurse on smaller partiton QuickSort(a, lo, i-1); // loop on larger lo = i+1; } else { QuickSort(a, i+1, hi); hi = i-1; } } }